Giả sử chúng ta có một chuỗi palindrome palindromic, chúng ta phải thay thế chính xác một ký tự bằng bất kỳ chữ cái tiếng Anh viết thường nào để chuỗi trở thành chuỗi nhỏ nhất có thể về mặt từ vựng mà không phải là palindrome. Bây giờ sau khi làm như vậy, chúng ta phải tìm chuỗi cuối cùng. Nếu không có cách nào để làm như vậy, thì hãy trả về chuỗi trống. Vì vậy, nếu đầu vào giống như "abccba", thì đầu ra sẽ là "aaccba".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
đã thay đổi:=false
-
nếu kích thước của một chuỗi là 1, thì trả về một chuỗi trống
-
i:=0 và j:=length of s - 1
-
leftA:=True and rightA:=True
-
trong khi tôi
-
nếu s [i] không phải là ‘a’, thì hãy đặt s [i] là ‘a’ và trả về s
-
tăng i lên 1 và giảm j đi 1
-
-
s [size of s - 1]:=‘b’
-
trả lại s
Ví dụ (C ++)
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:
string breakPalindrome(string s) {
bool changed = false;
if(s.size() == 1)return "";
int i = 0, j = s.size() - 1;
bool leftA = true;
bool rightA= true;
while(i < j){
if(s[i] != 'a'){
s[i] = 'a';
return s;
}
i++;
j--;
}
s[s.size() - 1] = 'b';
return s;
}
};
main(){
Solution ob;
cout << (ob.breakPalindrome("abccba"));
} Đầu vào
"abccba"
Đầu ra
aaccba