336. Palindrome Pairs

Palindrome Pairs
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

这道也是很复杂。Airbnb的高频。这道题有如下几个难点
1。两种match情况，不仔细的话很容易就没找到第二种。
2。bug free。这个真是太难一遍写干净了。这个一定要理清逻辑。
最优代码请直接看最后一个代码。

思路：
先建Trie树，常规操作，Trie结点里面需要存一下 word的index方便返回。
然后对每一个单词word，从它最后一个字母开始沿着Trie树查找。
每查找一个结点就要看下这个结点是不是某一个单词的结尾，如果是，则看一下word剩下的部分能不能够成palindrome，能的话就这就是一个结果要记下来。
如果查到一步， word还没扫完就查不下去了，直接返回。
这一步是一个很容易出bug的地方。
我们再来细细理一下逻辑。
首先test case里面空字符是可能存在的，所以我们要先判断root是不是，再进入for loop扫。

如果查完了 word, 还能查下去，那么对当前的结点做一个DFS，看哪些单词的剩余部分能组成palin。这个是很容易忘的地方。

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ans = new ArrayList<>();
        TrieNode root = new TrieNode('0');
        for (int i = 0; i < words.length; i++) {
            addToTrie(root, words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            List<Integer> matches = findMatches(words[i],  root);
            for (int match : matches) {
                if (match == i) continue;
                ans.add(Arrays.asList(match, i));
            }
        }
        return ans;
    }
    private void addToTrie(TrieNode root, String word, int index){
        for (int i = 0; i < word.length(); i++) {
            root = root.getOrCreate(word.charAt(i));
        }
        root.index = index;
        root.isWord = true;
    }
    private List<Integer> findMatches(String word, TrieNode root) {
        // go from word last char to first char;
        List<Integer> localAns = new ArrayList<>();
        if (root.isWord && isPalin(word, 0, word.length() - 1)) {
            localAns.add(root.index);
        }
        for (int i = word.length() - 1; i >= 0; i--) {
            root = root.get(word.charAt(i));
            if (root == null) return localAns;
            if (root.isWord && isPalin(word, 0, i - 1)) {
                localAns.add(root.index);
            }
        }
        findOtherMatches(root, new StringBuilder(), localAns);
        return localAns;
    }
    private void findOtherMatches(TrieNode root, StringBuilder sb, List<Integer> localAns) {
        if (root.isWord && sb.length() != 0) {
            if (isPalin(sb)) localAns.add(root.index);
        }
        for (TrieNode child : root.children.values()) {
            sb.append(child.c);
            findOtherMatches(child, sb, localAns);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    private boolean isPalin(String word, int l, int r) {
        while (l < r) {
            if(word.charAt(l++) != word.charAt(r--)) return false;
        }
        return true;
    }
    public boolean isPalin(StringBuilder sb) {
        int l = 0, r = sb.length() -1;
        while (l < r) {
            if (sb.charAt(l++) != sb.charAt(r--)) return false;
        }
        return true;
    }
}
class TrieNode {
    char c;
    int index;
    boolean isWord;
    Map<Character, TrieNode> children;
    public TrieNode(char c) {
        this.c = c;
        this.isWord = false;
        children = new HashMap<>();
    }
    public TrieNode getOrCreate(char ch) {
        children.putIfAbsent(ch, new TrieNode(ch));
        return children.get(ch);
    }
    public TrieNode get(char ch) {
        return children.get(ch);
    }
}

HashMap的解法，要短很多。
重要的是要去重，要用长的去找短的，可以把长的放在左边和把长的放在右边。
再找长度相等的。
在处理长match短的时候，一定要注意不要查找word整个length，可以查word的0 到 n - 1的length，（n种)
楼主最近又写了一遍，犯了下面几个错误。
1。循环变量用错了，该用i的地方用了j
2。加ans的时候忘了把它用Arrays.asList包起来。

上面的解释感觉不是很自然，有点绕。楼主又想了一种新的解释方法。
对于一个单词，如果它自己能找到他的镜像单词，直接放进去。
然后我们从左边一刀一刀砍，如果左边砍完之后剩下的右边的部分可以找到镜像，而砍去的那一部分本身也是对称的话，也成立。
然后我们从右边开始一刀一刀砍，。。。。同理

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ans = new ArrayList<>();
        // lls -> sll 
        Map<String, Integer> reverseMap = getReverseMap(words);
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            // abc -> cba
            if (reverseMap.containsKey(word) && reverseMap.get(word) != i) {
                ans.add(Arrays.asList(i, reverseMap.get(word)));
            }
            
            // abcdd ->looking for   cba 
            int l = word.length();
            for (int j = 0; j < l; j++) {
                if (isPalin(word, j, l - 1) && reverseMap.containsKey(word.substring(0, j))) {
                    ans.add(Arrays.asList(i, reverseMap.get(word.substring(0, j))));
                }
            }
            // def -> ggfed can't find def, can only find defgg ..   
            for (int j = l - 1; j >= 0; j --) {
                if (isPalin(word, 0, j) && reverseMap.containsKey(word.substring(j + 1, l))) {
                    ans.add(Arrays.asList(reverseMap.get(word.substring(j + 1, l)), i));
                }
            }
            

        }
        return ans;
    }
    private boolean isPalin(String w, int i, int j) {
        while (i < j) {
            if (w.charAt(i) != w.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
    private Map<String, Integer> getReverseMap(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            StringBuilder sb = new StringBuilder(word);
            sb.reverse();
            map.put(sb.toString(), i);
        }
        return map;
    }
}

一刀一刀砍的思路代码如下，感觉这样理解更自然。

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> revMap = buildMap(words);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (revMap.containsKey(word)) {
                if (revMap.get(word) != i)  ans.add(Arrays.asList(i, revMap.get(word)));
            }
            //chop right;
            int N = word.length();
            for (int r = N - 1; r >= 0; r--) {
                if (isPalin(word, r, N - 1) && revMap.containsKey(word.substring(0, r))) {
                    ans.add(Arrays.asList(i, revMap.get(word.substring(0, r))));
                }
            }
            //chop left;
            for (int l = 0; l < N; l++) {
                if (isPalin(word, 0, l) && revMap.containsKey(word.substring(l + 1, N))) {
                    ans.add(Arrays.asList(revMap.get(word.substring(l + 1, N)), i));
                }
            }
        }
        return ans;
    }
    private  Map<String, Integer> buildMap(String[] words) {
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            StringBuilder sb =  new StringBuilder(words[i]);
            sb.reverse();
            map.put(sb.toString(), i);
        }
        return map;
    }
    private boolean isPalin(String word, int l, int r) {
        while (l < r) {
            if (word.charAt(l++) != word.charAt(r--)) return false;
        }
        return true;
    }
}

336. Palindrome Pairs

推荐阅读更多精彩内容