Giả sử chúng ta có hai chuỗi s1 và s2 có kích thước bằng nhau; chúng ta phải kiểm tra xem một số hoán vị của chuỗi s1 có thể phá vỡ một số hoán vị của chuỗi s2 hoặc ngược lại. Chuỗi a có thể phá vỡ chuỗi b nếu x [i]> =y [i] (theo thứ tự bảng chữ cái) cho tất cả i trong phạm vi từ 0 đến n-1.
Vì vậy, nếu đầu vào giống như s1 =abc và s2 =xya, thì đầu ra sẽ là true. Điều này là do "ayx" là một hoán vị của s2 có thể phá vỡ thành chuỗi "abc" là một hoán vị của s1 ="abc".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm check (), điều này sẽ lấy s1, s2,
-
để khởi tạo i:=0, khi i
-
nếu s2 [i]
-
trả về false
-
-
-
trả về true
-
Từ phương thức chính, thực hiện như sau -
-
sắp xếp mảng s1
-
sắp xếp mảng s2
-
f3:=check (s2, s1)
-
f4:=check (s1, s2)
-
trả về true hoặc f3 là true hoặc f4 là true, ngược lại là false
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool check(string& s1, string& s2){
for (int i = 0; i < s1.size(); i++) {
if (s2[i] < s1[i])
return false;
}
return true;
}
bool checkIfCanBreak(string s1, string s2) {
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
bool f3 = check(s2, s1);
bool f4 = check(s1, s2);
return f3 || f4;
}
};
main(){
Solution ob;
cout << (ob.checkIfCanBreak("abc", "xya"));
} Đầu vào
"abc", "xya"
Đầu ra
1