Trong phần này, chúng ta sẽ xem cách kiểm tra xem hai chuỗi có phải là chuỗi meta hay không. Chuỗi meta là những chuỗi rất giống nhau. Nếu chúng ta hoán đổi hai phần tử trong một chuỗi, thì nó sẽ được khớp với chuỗi khác. Giả sử hai chuỗi là “HELLO” và “OELLH”, thì chúng là chuỗi meta.
Để kiểm tra xem hai chuỗi có phải là chuỗi meta hay không, chúng ta phải làm theo các bước sau.
Các bước -
-
Nếu cả hai chuỗi có độ dài khác nhau, thì trả về false
-
Ngoài ra, tìm một số ký tự chưa khớp, cũng lưu trữ chỉ mục của các ký tự không khớp
-
Nếu số lượng lớn hơn 2, thì trả về false
-
Nếu không, hãy hoán đổi các ký tự này, sau đó nếu hai chuỗi giống nhau thì trả về true, ngược lại là false.
Ví dụ
#include <iostream>
using namespace std;
bool areTheyMetaString(string s1, string s2) {
int s1_len = s1.length();
int s2_len = s2.length();
if (s1_len != s2_len)
return false;
int prev = -1, curr = -1;
int count = 0;
for (int i=0; i<s1_len; i++) {
if (s1[i] != s2[i]) {
count++; // number of unmatched characters
if (count > 2)
return false;
prev = curr;
curr = i;
}
}
return (count == 2 && s1[prev] == s2[curr] && s1[curr] == s2[prev]);
}
int main() {
string s1 = "HELLO", s2 = "OELLH";
if(areTheyMetaString(s1, s2)){
cout << "Meta Strings";
} else {
cout << "Not Meta Strings";
}
} Đầu ra
Meta Strings