C++의 회문 순열 II

문자열 s가 있다고 가정하고 모든 회문 순열을 찾아야 하고 반복은 없을 것입니다. 회문 순열이 없으면 단순히 빈 문자열을 반환합니다.

따라서 입력이 "aabb"와 같으면 출력은 ["abba", "baab"]

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

• ret 배열 정의

• solve() 함수를 정의하면 s, sz, 하나의 정렬되지 않은 맵 m, idx가 0으로 초기화,

• sz가 0과 같으면 -

  • ret 끝에 s 삽입

  • 반환

• evenFound :=거짓

• 방문한 한 세트 정의

• m의 각 키-값 쌍에 대해 다음을 수행합니다. -

  • 값이 0이면 -

    • (1씩 증가)

    • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

  • 그렇지 않으면 값이 1과 같을 때 -

    • oddChar :=키

  • 그렇지 않으면

    • 키를 방문하지 않으면

      • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

    • s[idx] :=키

    • s[크기 s - 1 - idx] =그것의 키

    • evenFound :=사실

    • m[키] :=m[키] - 2

    • 풀다(s, sz - 2, m, idx + 1)

    • m[키] :=m[키] + 2

    • 방문 키에 삽입

  • (1씩 증가)

• evenFound가 거짓이면 -

  • s[idx] :=oddChar

  • 풀다(s, sz - 1, m, idx + 1)

• 주요 방법에서 다음을 수행하십시오 -

• 하나의 맵 cnt 정의

• n :=s

  의 크기

• temp :=빈 문자열

• initialize i :=0의 경우, i

  • (cnt[s[i]]를 1씩 증가)

  • temp :=임시 연결 " * "

• 홀수Cnt :=0

• cnt의 각 키-값 쌍에 대해 다음을 수행합니다. -

  • 값이 홀수일 때 oddCount 증가

  • (1씩 증가)

• 만일 oddCnt> 1이면 -

  • 리턴 렛

• 해결(온도, n, cnt)

• 리턴 렛

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<string> ret;
   void solve(string s, int sz, unordered_map<char,int>& m, int idx = 0){
      if (sz == 0) {
         ret.push_back(s);
         return;
      }
      bool evenFound = false;
      char oddChar;
      unordered_map<char, int>::iterator it = m.begin();
      set<char> visited;
      while (it != m.end()) {
         if (!it->second) {
            it++;
            continue;
         }
         else if (it->second == 1) {
            oddChar = it->first;
         }
         else {
            if (visited.count(it->first))
               continue;
            s[idx] = it->first;
            s[s.size() - 1 - idx] = it->first;
            evenFound = true;
            m[it->first] -= 2;
            solve(s, sz - 2, m, idx + 1);
            m[it->first] += 2;
            visited.insert(it->first);
         }
         it++;
      }
      if (!evenFound) {
         s[idx] = oddChar;
         solve(s, sz - 1, m, idx + 1);
      }
   }
   vector<string< generatePalindromes(string s){
      unordered_map<char,int> cnt;
      int n = s.size();
      string temp = "";
      for (int i = 0; i < n; i++) {
         cnt[s[i]]++;
         temp += "*";
      }
      int oddCnt = 0;
      unordered_map<char, int>::iterator it = cnt.begin();
      while (it != cnt.end()) {
         oddCnt += (it->second & 1);
         it++;
      }
      if (oddCnt > 1)
         return ret;
      solve(temp, n, cnt);
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.generatePalindromes("aabb"));
}

입력

"aabb"

출력

[baab, abba, ]