สมมติว่าเรามีสตริงพาลินโดรม palindrome เราต้องแทนที่อักขระตัวเดียวด้วยตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กใด ๆ เพื่อให้สตริงกลายเป็นสตริงที่เล็กที่สุดเกี่ยวกับศัพท์เฉพาะที่ไม่ใช่ palindrome หลังจากทำอย่างนั้นแล้ว เราก็ต้องหาเส้นสุดท้าย หากไม่มีวิธีการดังกล่าว ให้ส่งคืนสตริงว่าง ดังนั้นหากอินพุตเป็นเหมือน “abccba” เอาต์พุตจะเป็น “aaccba”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เปลี่ยน :=เท็จ
-
หากขนาดของสตริงเท่ากับ 1 ให้คืนค่าสตริงว่าง
-
ผม :=0 และ j :=ความยาวของ s – 1
-
leftA :=จริงและ rightA :=จริง
-
ในขณะที่ฉัน
-
ถ้า s[i] ไม่ใช่ 'a' ให้ตั้งค่า s[i] เป็น 'a' แล้วคืนค่า s
-
เพิ่ม i 1 และลด j โดย 1
-
-
s[ขนาด s - 1] :='b'
-
ผลตอบแทน s
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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"));
} อินพุต
"abccba"
ผลลัพธ์
aaccba
