At first, I use the idea of Permutations to get all combinations, and then to detect whether they are palindrome.
The code is show below:
public class Solution {
public List<String> generatePalindromes(String s) {
List<String> result = new LinkedList<>();
if (s == null || s.length() == 0 ) return result;
List<Character> dict = new ArrayList<>();
HashSet<String> duplicates = new HashSet<>();
for(int i = 0; i < s.length(); i++){
dict.add(s.charAt(i));
}
StringBuilder sb = new StringBuilder();
helper(s,dict,sb,result,duplicates);
return result;
}
private void helper(String s, List<Character> dict, StringBuilder sb, List<String> result,HashSet<String> duplicates) {
if (sb.length() == s.length()){
String candidate = sb.toString();
if (isPalindrome(candidate) && !duplicates.contains(candidate))
result.add(candidate);
duplicates.add(candidate);
} else {
for (int i = 0; i < dict.size(); i++) {
char c = dict.get(i);
sb.append(c);
dict.remove(i);
helper(s,dict,sb,result,duplicates);
dict.add(c);
sb.deleteCharAt(sb.length()-1);
}
}
}
public boolean isPalindrome(String s) {
int begin = 0, end = s.length()-1;
while (begin < end) {
if (s.charAt(begin) !=s.charAt(end)){
return false;
} else {
begin++;
end--;
}
}
return true;
}
}
-------------------------------------------------------------------------------------------------------------------------------------
However, this method is TLE.
As I read the hint, I find out the reason. We only need to generate half of the string, the other half can be produced from the first part.
Remember they are palindrome :)
So, I modified the code:
