Giả sử chúng ta đã cho hai chuỗi ‘a’ và ‘b’, nhiệm vụ là tìm xem chúng ta có thể lấy được chuỗi ‘b’ hay không bằng cách xoay chuỗi ‘a’ chính xác hai vị trí theo hướng ngược chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Ví dụ:
Đầu vào-1 -
a = google b = legoog
Đầu ra -
True
Giải thích - Chuỗi ‘google’ có thể được xoay hai nơi theo hướng ngược chiều kim đồng hồ, điều này dẫn đến chuỗi ‘legoog’. Do đó, chúng tôi trả về True.
Đầu vào-2 -
a = tuorialst b = tutorials
Đầu ra -
False
Giải thích - Chuỗi ‘tuorialst’ không thể được xoay hai nơi theo bất kỳ hướng nào để lấy chuỗi ‘hướng dẫn’ khác. Do đó, chúng tôi trả về False.
Phương pháp được sử dụng để giải quyết vấn đề này
Đối với hai chuỗi đã cho, chúng ta có hai trường hợp trong cách tiếp cận này -
-
Để xoay ngược chiều kim đồng hồ
-
Đối với xoay theo chiều kim đồng hồ
Đầu tiên, nếu độ dài của cả hai chuỗi là khác nhau, thì trả về false. Ngược lại, nếu độ dài của cả hai chuỗi nhỏ hơn hoặc bằng ‘2’, thì chúng tôi sẽ trả về True.
Trong trường hợp khác, chúng tôi sẽ kiểm tra xem chuỗi con của chuỗi ‘b’ bằng cách xoay hai nơi theo chiều ngược chiều kim đồng hồ có bằng chuỗi ‘a’ hay không, khi đó chúng tôi sẽ trả về True. Ngược lại, Sai.
Tương tự, nếu bằng cách xoay chuỗi ‘b’ theo chiều kim đồng hồ bởi hai vị trí, nó trở thành bằng với chuỗi ‘a’, thì trả về True, ngược lại, chúng ta sẽ trả về false.
-
Lấy hai chuỗi nhập ‘a’ và ‘b’
-
Một hàm Boolean checkRotated (chuỗi a, chuỗi b) nhận hai chuỗi ‘a’ và ‘b’ và trả về nếu chúng bằng nhau bằng cách xoay chuỗi ‘b’ theo hướng ngược chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
-
Kiểm tra độ dài của chuỗi ‘a’ và chuỗi ‘b’.
-
Tìm chuỗi con của chuỗi ‘b’ bằng cách xoay hai vị trí ngược chiều kim đồng hồ.
-
Bây giờ, hãy kiểm tra xem chuỗi con kết quả có bằng chuỗi ‘a’ hay không và trả về true nếu nó bằng.
-
Tìm chuỗi con của chuỗi ‘b’ bằng cách xoay nó ở hai nơi theo chiều kim đồng hồ.
-
Bây giờ, hãy kiểm tra xem chuỗi con kết quả có bằng chuỗi ‘a’ hay không và trả về true nếu nó bằng.
-
Nếu các chuỗi không bằng nhau, thì trả về false.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
bool checkRotated(string str1, string str2){
if (str1.length() != str2.length())
return false;
if(str1.length() <= 2 || str2.length() <= 2)
return (str1 == str2);
string s1= str2.substr(str2.size()-2, str2.size());
string s2= str2.substr(0,str2.size()-2);
string s3= s1+s2;
if(s3==str1)
return true;
string s4= str2.substr(2,str2.size());
string s5= str2.substr(0,2);
string s6= s4+s5;
if(s6==str1)
return true;
return false;
}
int main(){
string a= "google";
string b="legoog";
cout<<checkRotated(a,b)<<endl;
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ in ra kết quả là,
1
Vì đầu ra của đoạn mã trên là "True", nó sẽ in ra "1".