0336. Palindrome Pairs

https://leetcode.com/problems/palindrome-pairs

Description

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

Example 1:

**Input:** words = ["abcd","dcba","lls","s","sssll"]
**Output:** [[0,1],[1,0],[3,2],[2,4]]
**Explanation:** The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

**Input:** words = ["bat","tab","cat"]
**Output:** [[0,1],[1,0]]
**Explanation:** The palindromes are ["battab","tabbat"]

Example 3:

**Input:** words = ["a",""]
**Output:** [[0,1],[1,0]]

Constraints:

• 1 <= words.length <= 5000

• 0 <= words[i].length <= 300

• words[i] consists of lower-case English letters.

ac1: split word

one important idea in palindrome is cutting the string into 2 parts and check palindrome.

https://leetcode.com/problems/palindrome-pairs/discuss/79199/150-ms-45-lines-JAVA-solution/242203

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        // edge cases
        if (words == null || words.length <= 1) return res;

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }

        for (int i = 0; i < words.length; i++) {
            String curr = words[i];
            for (int j = 0; j <= curr.length(); j++) {
                String left = curr.substring(0, j);
                String right = curr.substring(j);

                // check left side
                if (isPalindrome(left)) { // left side is palindrome, check the rest
                    String rightReversed = new StringBuilder().append(right).reverse().toString();
                    if (map.containsKey(rightReversed) && map.get(rightReversed) != i) {  // cannot be itself, like "a"
                        res.add(Arrays.asList(map.get(rightReversed), i)); // found, append to the left
                    }
                }

                // check right side
                if (right.length() != 0 && isPalindrome(right)) { // right.length() != 0 avoid duplicate, like "abc", when left is "", this has been processed.
                    String leftReversed = new StringBuilder().append(left).reverse().toString();
                    if (map.containsKey(leftReversed)) {
                        res.add(Arrays.asList(i, map.get(leftReversed))); // found, append to the right
                    }
                }
            }
        }

        return res;
    }

    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l <= r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}
/*
hashmap
*/

ac2: Trie

Way too complicated. https://leetcode.com/problems/palindrome-pairs/discuss/79195/O(n-*-k2)-java-solution-with-Trie-structure

private static class TrieNode {
    TrieNode[] next;
    int index;
    List<Integer> list;

    TrieNode() {
        next = new TrieNode[26];
        index = -1;
        list = new ArrayList<>();
    }
}

public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> res = new ArrayList<>();

    TrieNode root = new TrieNode();

    for (int i = 0; i < words.length; i++) {
        addWord(root, words[i], i);
    }

    for (int i = 0; i < words.length; i++) {
        search(words, i, root, res);
    }

    return res;
}

private void addWord(TrieNode root, String word, int index) {
    for (int i = word.length() - 1; i >= 0; i--) {
        int j = word.charAt(i) - 'a';

        if (root.next[j] == null) {
            root.next[j] = new TrieNode();
        }

        if (isPalindrome(word, 0, i)) {
            root.list.add(index);
        }

        root = root.next[j];
    }

    root.list.add(index);
    root.index = index;
}

private void search(String[] words, int i, TrieNode root, List<List<Integer>> res) {
    for (int j = 0; j < words[i].length(); j++) {   
        if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) {
            res.add(Arrays.asList(i, root.index));
        }

        root = root.next[words[i].charAt(j) - 'a'];
        if (root == null) return;
    }

    for (int j : root.list) {
        if (i == j) continue;
        res.add(Arrays.asList(i, j));
    }
}

private boolean isPalindrome(String word, int i, int j) {
    while (i < j) {
        if (word.charAt(i++) != word.charAt(j--)) return false;
    }

    return true;
}