C++에서 회문 깨기

회문 문자열 회문이 있다고 가정하고 정확히 한 문자를 소문자 영어 문자로 바꿔야 문자열이 회문이 아닌 사전순으로 가능한 가장 작은 문자열이 됩니다. 이제 그렇게 하고 나면 최종 문자열을 찾아야 합니다. 방법이 없으면 빈 문자열을 반환합니다. 따라서 입력이 "abccba"와 같으면 출력은 "aaccba"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 변경됨 :=거짓

• 문자열의 크기가 1이면 빈 문자열을 반환합니다.

• i :=0 및 j :=s – 1의 길이

• leftA :=True 및 rightA :=True

• 동안 나는

  • 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