[Code Redo] 40 Lines O(N*K) Solution Using KMP


  • 0
    O

    This is a redo of

    https://leetcode.com/discuss/92393/a-130ms-o-n-k-solution-using-kmp

    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            int n = words.length;
            boolean[][] v = new boolean[n][n];
            HashMap<String, Integer> h = new HashMap();
            List<List<Integer>> ans = new ArrayList();
            for (int i = 0; i < words.length; h.put(words[i], i), v[i][i] = true, i++);
            
            for (int i = 0; i < n; i++) {
                List<String> palinMatch = findPalinMatch(words[i]);
                for (String cand : palinMatch)
                    if (h.containsKey(cand) && !v[h.get(cand)][i]) {
                        ans.add(Arrays.asList(h.get(cand), i));
                        v[h.get(cand)][i] = true;
                    }
                        
                palinMatch = findPalinMatch(new StringBuilder(words[i]).reverse().toString());
                for (String cand : palinMatch) {
                    String candR = new StringBuilder(cand).reverse().toString();
                    if (h.containsKey(candR) && !v[i][h.get(candR)]) {
                        ans.add(Arrays.asList(i, h.get(candR)));
                        v[i][h.get(candR)] = true;
                    }
                }
            }
            
            return ans;
        }
        
        private List<String> findPalinMatch(String s) {
            String y = s + "#" + new StringBuilder(s).reverse().toString();
            int len = y.length();
            int[] p = new int[len]; // find KMP table
            p[0] = 0;
            for (int i = 1; i < len; i++) {
                int j = p[i - 1];
                while (j > 0 && y.charAt(i) != y.charAt(j)) j = p[j - 1];
                p[i] = (y.charAt(i) != y.charAt(j)) ? 0 : j + 1;
            }
            
            List<String> res = new ArrayList();
            for (int j = p[len - 1]; j > 0; j = p[j - 1])
                res.add(y.substring(len - s.length(), len - j));
            res.add(y.substring(len - s.length()));
            return res;    
        }
    }
    
    //183ms

  • 0
    O

    The mindset is to take use of best-voted solution of No. 214 problem, "shortest palindrome". In this problem, you not only need to find the match to construct shortest palindrome, you try to construct every possible palindrome using the returned KMP table.


  • 0
    O
    public class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> ans = new LinkedList();
            int n = words.length;
            Map<String, Integer> h = new HashMap();
            boolean[][] used = new boolean[n][n];
            for (int i = 0; i < n; i++) h.put(words[i], i);
            for (int i = 0; i < n; i++) findPairs(i, words[i], h, ans, used);
            return ans;
        }
        
        private void findPairs(int idx, String str, Map<String, Integer> h, List<List<Integer>> ans, boolean[][] used) {
            boolean onLeft = true;
            addPairs(idx, str, h, ans, onLeft, used);
            addPairs(idx, str, h, ans, !onLeft, used);
        }
        
        private void addPairs(int idx, String str, Map<String, Integer> h, List<List<Integer>> ans, boolean onLeft, boolean[][] used) {
            String rev = new StringBuilder(str).reverse().toString();
            String con = onLeft ? str + '#' + rev : rev + '#' + str;
            List<String> cands = findPalin(con, str.length());
            for (String cand : cands) {
                if (!onLeft) cand = new StringBuilder(cand).reverse().toString();
                //System.out.println("find " + cand + " on " + onLeft + " of " + str);
                int t = h.containsKey(cand) ? h.get(cand) : -1;
                if (t >= 0 &&  t != idx && ((onLeft && !used[t][idx]) || (!onLeft && !used[idx][t]))) {
                    //System.out.println("adding " + idx + ", " + h.get(cand));
                    List<Integer> cur = new LinkedList();
                    cur.add(idx);
                    if (onLeft) {
                        cur.add(0, t); 
                        used[t][idx] = true;
                        } else {
                        cur.add(t);
                        used[idx][t] = true;
                        }
                    ans.add(cur);
                }
            }
        }
        
        private List<String> findPalin(String con, int lenHalf) {
            List<Integer> l = findKMP(con);
            List<String> res = new ArrayList();
            int len = con.length();
            if (len > 1)
                for (int i : l)
                    res.add(con.substring(len - lenHalf, len - i));
            return res;
        }
        
        private List<Integer> findKMP(String s) {
            char[] c = s.toCharArray();
            int len = c.length;
            int[] p = new int[len];
            for (int i = 1, j = 0; i < len; i++) {
                while (j > 0 && c[j] != c[i]) j = p[j - 1];
                if (c[j] == c[i]) j++;
                p[i] = j;
                //System.out.print(p[i] + ", ");
            }   //System.out.println(".");
            
            List<Integer> res = new ArrayList();
            res.add(0);
            res.add(1); 
            for (int j = p[len - 1]; j > 1; j = p[j - 1]) res.add(j);
            return res;
        }
    }
    
    //186ms - 3rd time redo

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.