BiruLyu
6/26/2017 - 11:49 PM

336. Palindrome Pairs(Trie).java

``````public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (words == null || words.length < 2) return res;
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < words.length; i++) {
map.put(words[i], i);
}
for (int i = 0; i < words.length; i++) {
for (int j = 0; j <= words[i].length(); j++) {// // notice it should be "j <= words[i].length()"  ["a",""] => [[0,1],[1,0]]
String str1 = words[i].substring(0, j);
String str2 = words[i].substring(j);
if (isPalindrome(str1)) {
String reverse = new StringBuilder(str2).reverse().toString();
if (map.containsKey(reverse) && map.get(reverse) != i) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(map.get(reverse));
temp.add(i);
res.add(temp);
}
}
if (isPalindrome(str2)) {
String reverse = new StringBuilder(str1).reverse().toString();
if (map.containsKey(reverse) && map.get(reverse) != i && str2.length()!= 0) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(i);
temp.add(map.get(reverse));
res.add(temp);
}
}
}
}
return res;

}

public boolean isPalindrome (String str) {
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left++) != str.charAt(right--)) return false;
}
return true;
}
}``````
``````public class Solution {
public static class Trie {
int pos;
Trie[] nodes;   // consider xyxabc. if current trie is 'a'. Then a.nodes has information. It means string after a is palindrome
List<Integer> palins;
public Trie() {
pos = -1;
nodes = new Trie[26];
palins = new ArrayList<>();
}
}

public static void add(Trie root, String word, int pos) {
for (int i = word.length() - 1; i >= 0; i--) {
char ch = word.charAt(i);
if (isPalindrome(word, 0, i)) { // check if substring(0, i) is palindrome.
root.palins.add(pos);
}
if (root.nodes[ch - 'a'] == null) {
root.nodes[ch - 'a'] = new Trie();
}
root = root.nodes[ch - 'a'];
}
root.pos = pos; // if it is xyxcba. Until now, the node should be at x.
root.palins.add(pos);
}

public static void search(Trie root, String[] words, int i, List<List<Integer>> ans) {
int len = words[i].length();
for (int j = 0; j < len && root != null; j++) {
if (root.pos >= 0 && i != root.pos && isPalindrome(words[i], j, len - 1)) {
ans.add(Arrays.asList(new Integer[] {i, root.pos}));
}
char ch = words[i].charAt(j);
root = root.nodes[ch - 'a'];
}
if (root != null && root.palins.size() > 0) { // assume 'xyxabc' is in trie, now try 'cba'
for (int j : root.palins) {
if (j != i) {
ans.add(Arrays.asList(new Integer[] {i, j}));
}
}
}
}

public static List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ans = new ArrayList<>();
Trie trie = new Trie();
for (int i = 0; i < words.length; i++) {
add(trie, words[i], i);
}
for (int i = 0; i < words.length; i++) {
search(trie, words, i, ans);
}
return ans;
}

public static boolean isPalindrome(String str, int i, int j) {
while (i < j) {
if (str.charAt(i++) != str.charAt(j--)) {
return false;
}
}
return true;
}
}``````