A 130ms O(n*k) solution using KMP


  • 0
    O

    well, we may observe that for example:
    s = "catacb"
    we want to add "b" to its left.
    Should I find the max palindrome start from left 0? Yes.

    What if
    s = "cacacb"?
    we want to add "b" to its left.
    we also want to try to add "bca" to it.
    That means not only we need find max plindrome start from 0, but also any palindrome which is shorter but exist.

    There is a solution in https://leetcode.com/discuss/64309/clean-kmp-solution-with-super-detailed-explanation, which solves how to find max palindrome start from 0. The explanation is great. Thanks for hpplayer's work. So I reckon that maybe I can continue to find any sub palindrome from the existing KMP searching solutions.

    The fact is, for example, you solve "cacacb" by solve "cacacb#bcacac" KMP table, you get:
    array p = 0,0,1,2,3,0,0,0,1,2,3,4,5
    p[last element] = 5 is the max palindrome length start from index 0 of "cacacb", which is "cacac"
    p[5 - 1] = 3 is the next sub palindrome length start from index 0 of "cacacb", which is "cac"

    What's more, you need to also try to put strings to the right of string:
    cacab +> acac
    which means you need to also solve the extended string reversely and find and palindrome that ends at last element of the string.

    Apology for my messy explanation. Have to run for lab work....

    public class Solution {
    private int[] calKMP(String s) {  //return KMP prefix table
        int len = s.length();
        int[] p = new int[len];
        for (int i = 1; i < len; i++) {
            int j = p[i - 1];
            while (j > 0 && s.charAt(j) != s.charAt(i)) j = p[j - 1];
            p[i] = s.charAt(j) == s.charAt(i) ? j + 1 : j;
        }
        return p;
    }
    
    private void addTo(List<List<Integer>> ansList, int i, String sAdd, boolean toLeft, boolean[][] has, HashMap<String, Integer> h) {
        if (!h.containsKey(sAdd)) return; 
        int j = h.get(sAdd);
        if (toLeft) { //put string index j to the left of i
            if (has[j][i]) return; // avoid repeating
            ArrayList<Integer> aSolution = new ArrayList<Integer>();
            aSolution.add(j);
            aSolution.add(i);
            has[j][i] = true;
            ansList.add(aSolution);
        } else { // put j to the right of i
            if (has[i][j]) return; // avoid repeating
            ArrayList<Integer> aSolution = new ArrayList<Integer>();
            aSolution.add(i);
            aSolution.add(j);
            has[i][j] = true;
            ansList.add(aSolution);            
        }
    }
    
    public List<List<Integer>> palindromePairs(String[] words) {
        boolean toLeft = true;
        int n = words.length;
        List<List<Integer>> ansList = new ArrayList<List<Integer>>();
        HashMap<String, Integer> h = new HashMap<String, Integer>();
        boolean[][] has = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            h.put(words[i], i);
            has[i][i] = true;
        }
        
        for (int i = 0; i < n; i++) {
            int len = words[i].length();
            if (len == 0) continue;
            String sRev = new StringBuffer(words[i]).reverse().toString();
            addTo(ansList, i, sRev, toLeft, has, h);
            addTo(ansList, i, sRev, !toLeft, has, h);
            addTo(ansList, i, sRev.substring(0, len - 1), toLeft, has, h);
            addTo(ansList, i, sRev.substring(1), !toLeft, has, h);
            
            String sP = words[i] + '#' + sRev, sQ = sRev + '#' + words[i];
            int[] p = calKMP(sP), q = calKMP(sQ);
            int lenExt = 2 * len + 1, j = p[lenExt - 1];
            //System.out.println("<" + words[i] + ">'s <" + sP + "> KMP table:");
            //for (int k = 0; k < lenExt; k++) System.out.print(p[k] + ","); System.out.println(".");
            while (j > 1) {
                addTo(ansList, i, sRev.substring(0, len - j), toLeft, has, h);
                //System.out.println("try add to ans list: " + sRev.substring(0, len - j) + "<+" + words[i]);
                j = p[j - 1];
            }
            //System.out.println("<" + words[i] + ">'s <" + sQ + "> KMP table:");
            //for (int k = 0; k < lenExt; k++) System.out.print(q[k] + ","); System.out.println(".");
            j = q[lenExt - 1];
            while (j > 1) {
                addTo(ansList, i, sRev.substring(j), !toLeft, has, h);
                //System.out.println("try add to ans list: " + words[i] + "+>" + sRev.substring(j));
                j = q[j - 1];
            }
        }
        return ansList;
    }
    

    }

    I also print to you the working internal output during the process. Hope you would get a clue:

    Your input
    
    ["abcd", "dcba", "lls", "s", "sssll", "catacb", "catacatacb", "cacacb"]
    Your stdout
    
    <abcd>'s <abcd#dcba> KMP table:
    0,0,0,0,0,0,0,0,1,.
    <abcd>'s <dcba#abcd> KMP table:
    0,0,0,0,0,0,0,0,1,.
    <dcba>'s <dcba#abcd> KMP table:
    0,0,0,0,0,0,0,0,1,.
    <dcba>'s <abcd#dcba> KMP table:
    0,0,0,0,0,0,0,0,1,.
    <lls>'s <lls#sll> KMP table:
    0,1,0,0,0,1,2,.
    try add to ans list: s<+lls
    <lls>'s <sll#lls> KMP table:
    0,0,0,0,0,0,1,.
    <s>'s <s#s> KMP table:
    0,0,1,.
    <s>'s <s#s> KMP table:
    0,0,1,.
    <sssll>'s <sssll#llsss> KMP table:
    0,1,2,0,0,0,0,0,1,2,3,.
    try add to ans list: ll<+sssll
    try add to ans list: lls<+sssll
    <sssll>'s <llsss#sssll> KMP table:
    0,1,0,0,0,0,0,0,0,1,2,.
    try add to ans list: sssll+>sss
    <catacb>'s <catacb#bcatac> KMP table:
    0,0,0,0,1,0,0,0,1,2,3,4,5,.
    try add to ans list: b<+catacb
    <catacb>'s <bcatac#catacb> KMP table:
    0,0,0,0,0,0,0,0,0,0,0,0,1,.
    <catacatacb>'s <catacatacb#bcatacatac> KMP table:
    0,0,0,0,1,2,3,4,5,0,0,0,1,2,3,4,5,6,7,8,9,.
    try add to ans list: b<+catacatacb
    try add to ans list: bcata<+catacatacb
    <catacatacb>'s <bcatacatac#catacatacb> KMP table:
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,.
    <cacacb>'s <cacacb#bcacac> KMP table:
    0,0,1,2,3,0,0,0,1,2,3,4,5,.
    try add to ans list: b<+cacacb
    try add to ans list: bca<+cacacb
    <cacacb>'s <bcacac#cacacb> KMP table:
    0,0,0,0,0,0,0,0,0,0,0,0,1,.
    Your answer
    
    [[1,0],[0,1],[3,2],[2,4]]

  • 0
    H
    This post is deleted!

Log in to reply
 

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