Skip to content

Latest commit

 

History

History
282 lines (263 loc) · 7.69 KB

336. Palindrome Pairs.md

File metadata and controls

282 lines (263 loc) · 7.69 KB

336. Palindrome Pairs

leetcode-cn Daily Challenge on August 6th, 2020.

Difficulty : Hard

Related Topics : HashTable、String、Trie

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.

Example 1:

Input: ["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: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Solution

  • mine
    • Java
      • TLE--Time Limited Exceeded 
        // O(N^2 * M)time
// O(M)space
// M = avg(len(word))
public List<List<Integer>> palindromePairs(String[] words) {
    int n = words.length;
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (check(words[i] + words[j])) {
                res.add(new ArrayList<>(Arrays.asList(i, j)));
            }
        }
    }
    return res;
}

boolean check(String word) {
    int l = 0, r = word.length() - 1;
    char[] arr = word.toCharArray();
    while (l <= r) {
        if (arr[l++] != arr[r--]) return false;
    }
    return true;
}
  • the most votes
  • Runtime: 77 ms, faster than 64.59%, Memory Usage: 115.5 MB, less than 6.10% of Java online submissions 
    // O(N * M^2)time
// O(N * M)space
// M = avg(len(word))
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;
}

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

    TrieNode() {
        next = new TrieNode[26];
        index = -1;
        list = new ArrayList<>();
    }
}
  • leetcode solution
  • Manacher Runtime: 179 ms, faster than 25.84%, Memory Usage: 49.9 MB, less than 6.10% of Java online submissions 
    // O(N * M)time
// O(N * M)space
// M = avg(len(word))
public List<List<Integer>> palindromePairs(String[] words) {
    Trie trie1 = new Trie();
    Trie trie2 = new Trie();

    int n = words.length;
    for (int i = 0; i < n; i++) {
        trie1.insert(words[i], i);
        StringBuffer tmp = new StringBuffer(words[i]);
        tmp.reverse();
        trie2.insert(tmp.toString(), i);
    }

    List<List<Integer>> ret = new ArrayList<List<Integer>>();
    for (int i = 0; i < n; i++) {
        int[][] rec = manacher(words[i]);

        int[] id1 = trie2.query(words[i]);
        words[i] = new StringBuffer(words[i]).reverse().toString();
        int[] id2 = trie1.query(words[i]);

        int m = words[i].length();

        int allId = id1[m];
        if (allId != -1 && allId != i) {
            ret.add(Arrays.asList(i, allId));
        }
        for (int j = 0; j < m; j++) {
            if (rec[j][0] != 0) {
                int leftId = id2[m - j - 1];
                if (leftId != -1 && leftId != i) {
                    ret.add(Arrays.asList(leftId, i));
                }
            }
            if (rec[j][1] != 0) {
                int rightId = id1[j];
                if (rightId != -1 && rightId != i) {
                    ret.add(Arrays.asList(i, rightId));
                }
            }
        }
    }
    return ret;
}

public int[][] manacher(String s) {
    int n = s.length();
    StringBuffer tmp = new StringBuffer("#");
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            tmp.append('*');
        }
        tmp.append(s.charAt(i));
    }
    tmp.append('!');
    int m = n * 2;
    int[] len = new int[m];
    int[][] ret = new int[n][2];
    int p = 0, maxn = -1;
    for (int i = 1; i < m; i++) {
        len[i] = maxn >= i ? Math.min(len[2 * p - i], maxn - i) : 0;
        while (tmp.charAt(i - len[i] - 1) == tmp.charAt(i + len[i] + 1)) {
            len[i]++;
        }
        if (i + len[i] > maxn) {
            p = i;
            maxn = i + len[i];
        }
        if (i - len[i] == 1) {
            ret[(i + len[i]) / 2][0] = 1;
        }
        if (i + len[i] == m - 1) {
            ret[(i - len[i]) / 2][1] = 1;
        }
    }
    return ret;
}

class Trie {
    List<Node> tree = new ArrayList<Node>();

    public Trie() {
        tree.add(new Node());
    }

    public void insert(String s, int id) {
        int len = s.length(), add = 0;
        for (int i = 0; i < len; i++) {
            int x = s.charAt(i) - 'a';
            if (tree.get(add).ch[x] == 0) {
                tree.add(new Node());
                tree.get(add).ch[x] = tree.size() - 1;
            }
            add = tree.get(add).ch[x];
        }
        tree.get(add).flag = id;
    }

    public int[] query(String s) {
        int len = s.length(), add = 0;
        int[] ret = new int[len + 1];
        Arrays.fill(ret, -1);
        for (int i = 0; i < len; i++) {
            ret[i] = tree.get(add).flag;
            int x = s.charAt(i) - 'a';
            if (tree.get(add).ch[x] == 0) {
                return ret;
            }
            add = tree.get(add).ch[x];
        }
        ret[len] = tree.get(add).flag;
        return ret;
    }

    class Node {
        int[] ch = new int[26];
        int flag;

        public Node() {
            flag = -1;
        }
    }
}