Palindrome Permutation II trong C ++

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm tất cả các hoán vị palindromic của nó, sẽ không có sự lặp lại. Nếu không có hoán vị palindromic ở đó, thì chỉ cần trả về chuỗi trống.

Vì vậy, nếu đầu vào là "aabb", thì đầu ra sẽ là ["abba", "baab"]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định ret mảng

• Xác định một hàm giải quyết (), điều này sẽ lấy s, sz, một bản đồ không có thứ tự m, idx khởi tạo nó bằng 0,

• nếu sz giống 0 thì -

  • chèn s vào cuối ret

  • trở lại

• EvenFound:=false

• Xác định một tập hợp đã truy cập

• đối với mỗi cặp khóa-giá trị, nó là m, do -

  • nếu giá trị của nó bằng 0, thì -

    • (tăng nó lên 1)

    • Bỏ qua phần sau, chuyển sang phần tiếp theo

  • ngược lại khi giá trị của nó bằng 1 thì -

    • lẻChar:=key của nó

  • Nếu không

    • nếu khóa của nó không được truy cập, thì

      • Bỏ qua phần sau, chuyển sang phần tiếp theo

    • s [idx]:=key of it

    • s [size of s - 1 - idx] =key of it

    • EvenFound:=true

    • m [key of it]:=m [key of it] - 2

    • giải quyết (s, sz - 2, m, idx + 1)

    • m [key of it]:=m [key of it] + 2

    • chèn chìa khóa của nó vào đã truy cập

  • (tăng nó lên 1)

• nếu Even Tìm sai, thì -

  • s [idx]:=retailChar

  • giải quyết (s, sz - 1, m, idx + 1)

• Từ phương thức chính, thực hiện như sau -

• Xác định một bản đồ cnt

• n:=kích thước của s

• temp:=chuỗi trống

• để khởi tạo i:=0, khi i

  • (tăng cnt [s [i]] lên 1)

  • temp:=temp nối "*"

• lẻCnt:=0

• cho mỗi cặp khóa-giá trị trong cnt, do -

  • tăng số lẻ khi giá trị của nó là số lẻ

  • (tăng nó lên 1)

• nếu lẻCnt> 1 thì -

  • trả lại ret

• giải quyết (tạm thời, n, cnt)

• trả lại ret

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;
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"));
}

Đầu vào

"aabb"

Đầu ra

[baab, abba, ]