Bài tập  /  Bài đang cần trả lời

Hai xâu kí tự S1 và S2 được gọi là hai xâu họ hàng nếu mỗi kí tự có ở xâu này đều có ở xâu kia và ngược lại

Hai xâu kí tự S1 và S2 được gọi là hai xâu họ hàng nếu mỗi kí tự có ở xâu này đều
có ở xâu kia và ngược lại. Hai xâu rỗng cũng được xem là hai xâu họ hàng.
Ví dụ: S1 = ‘aabccdcbe’; S2 = ‘abcde’ là hai xâu họ hàng.
Yêu cầu: Nhập từ bàn phím hai xâu kí tự S1 và S2 (tối đa 255 kí tự) chỉ chứa chữ
cái thường và không phải là hai xâu họ hàng. Hãy tìm cách xóa ít nhất một số kí tự ở
mỗi xâu (cũng có thể chỉ xóa ở một xâu) để được hai xâu kí tự mới là hai xâu họ hàng.
1 Xem trả lời
Hỏi chi tiết
267
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để giải bài toán này, ta có thể sử dụng thuật toán Greedy. Ý tưởng của thuật toán là xóa các kí tự không cần thiết trong cả hai xâu cho đến khi hai xâu trở thành hai xâu họ hàng.

Bước 1: Đếm số lần xuất hiện của mỗi kí tự trong cả hai xâu.

Bước 2: Duyệt qua từng kí tự trong mỗi xâu. Nếu kí tự đó không có trong xâu kia, ta xóa nó khỏi xâu hiện tại.

Bước 3: Lặp lại bước 2 cho đến khi không còn kí tự nào cần xóa.

Dưới đây là mã giả của thuật toán:

```
def remove_characters(s1, s2):
# Bước 1: Đếm số lần xuất hiện của mỗi kí tự trong cả hai xâu
count1 = [0] * 26
count2 = [0] * 26
for c in s1:
count1[ord(c) - ord('a')] += 1
for c in s2:
count2[ord(c) - ord('a')] += 1

# Bước 2: Xóa các kí tự không cần thiết trong cả hai xâu
i = 0
while i < len(s1):
c = s1[i]
if count2[ord(c) - ord('a')] == 0:
s1 = s1[:i] + s1[i+1:]
else:
i += 1

i = 0
while i < len(s2):
c = s2[i]
if count1[ord(c) - ord('a')] == 0:
s2 = s2[:i] + s2[i+1:]
else:
i += 1

# Bước 3: Lặp lại bước 2 cho đến khi không còn kí tự nào cần xóa
while True:
removed = False

i = 0
while i < len(s1):
c = s1[i]
if count2[ord(c) - ord('a')] == 0:
s1 = s1[:i] + s1[i+1:]
removed = True
else:
i += 1

i = 0
while i < len(s2):
c = s2[i]
if count1[ord(c) - ord('a')] == 0:
s2 = s2[:i] + s2[i+1:]
removed = True
else:
i += 1

if not removed:
break

return s1, s2
```

Sau khi thực hiện hàm `remove_characters(s1, s2)`, ta sẽ nhận được hai xâu mới là hai xâu họ hàng.
1
0
Ngoc Trinh
18/01/2024 20:32:02
+5đ tặng
  • #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    int main ()
    {
      string str1, str2;
      cin >> str1 >> str2;
      vector <char>s1 (str1.begin (), str1.end ());
      vector <char>s2 (str2.begin (), str2.end ());
    ll dem = 0,i=0;
      while (i<s1.size ())
        {
         while (find (s2.begin (), s2.end (), s1[i]) == s2.end ())
     {s1.erase (s1.begin () + i);
       dem++;
     }
          i++;
        }
      i = 0;
      while (i < s2.size ())
        {
          while (find (s1.begin (), s1.end (), s2[i]) == s1.end ())
     {
       s2.erase (s2.begin () + i);
       dem++;
     }
          i++;
        }
        cout << dem;
    }

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường
×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500k
Gửi câu hỏi
×