LeetCode [267] Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example 1:

Input: "aabb"
Output: ["abba", "baab"]

Example 2:

Input: "abc"
Output: []

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { public: bool wordPatternMatch(string pattern, string str) { unordered_map<char, string> hash1; unordered_map<string, char> hash2; return bt(pattern, str, 0, 0, pattern.size(), str.size(), hash1, hash2); } bool bt(string &pattern, string &str, int p, int s, int np, int ns, unordered_map<char, string> &hash1, unordered_map<string, char> &hash2){ if(p==np && s==ns){ return true; }else if(p<np && s<ns){ char c = pattern[p]; if(hash1.count(c)){ int len = hash1[c].size(); if(s+len<=ns && str.substr(s, len)==hash1[c] && bt(pattern, str, p+1, s+len, np, ns, hash1, hash2)){ return true; }else{ return false; } }else{ for(int i=s; i<ns; ++i){ string ss = str.substr(s, i-s+1); if(hash2.count(ss)==0){ hash1[c] = ss; hash2[ss] = c; if(bt(pattern, str, p+1, i+1, np, ns, hash1, hash2)) return true; hash2.erase(ss); hash1.erase(c); } } } } return false; } };