214. Shortest Palindrome (Hard)

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

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

Solutions

class Solution {

    private int match(String s, String p) {
        char[] str = s.toCharArray();
        char[] pattern = p.toCharArray();

        int[] next = getNextArray2(pattern);

        int strPtr = 0;
        int patternPtr = 0;

        while (strPtr > patternPtr) {
            if (patternPtr == -1) {
                patternPtr++;
                strPtr++;
            } else if (pattern[patternPtr] == str[strPtr]) {
                patternPtr++;
                strPtr++;
            } else {
                patternPtr = next[patternPtr];
            }
        }

        if (patternPtr == p.length()) {
            return strPtr - p.length();
        }

        return -1;
    }

    public String shortestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        int len = s.length();

        char[] str = s.toCharArray();
        char[] pattern = s.toCharArray();

        int[] next = getNextArray(pattern);

        int strPtr = len - 1;
        int patternPtr = 0;

        while (strPtr > patternPtr) {
            if (patternPtr == -1) {
                patternPtr++;
                strPtr--;
            } else if (pattern[patternPtr] == str[strPtr]) {
                patternPtr++;
                strPtr--;
            } else {
                patternPtr = next[patternPtr];
            }
        }

        int palLen = 0;

        // if patternPtr == 0, palLen should be 1

        if (strPtr == patternPtr) {
            // patternPtr is index
            palLen = (patternPtr + 1) * 2 - 1;
        } else {
            // patternPtr is index
            palLen = patternPtr * 2;
        }

        String ans = s;

        // FIXME Do not use following method that concatenate the chars which trigger time limit exceeding, use StringBuild instead.

//            for (int i = palLen; i < len; i++) {
//                ans = s.charAt(i) + ans;
//            }

        ans = new StringBuilder(s.substring(palLen)).reverse().toString() + ans;

        return ans;
    }

    // Incorrect method
    private int[] getNextArray(char[] pattern) {
        int len = pattern.length;

        int[] next = new int[len];

        next[0] = -1;
        next[1] = 0;

        for (int i = 2; i < len; i++) {
            int lastMatchedCount = next[i - 1];

            if (pattern[lastMatchedCount] == pattern[i - 1]) {
                next[i] = next[i - 1] + 1;
            } else if (pattern[0] == pattern[i - 1]) {
                next[i] = 1;
            } else {
                next[i] = 0;
            }
        }

        return next;
    }

    // Correct method

    public int[] getNextArray2(char[] pattern) {
        int[] next = new int[pattern.length];

        next[0] = -1;
        next[1] = 0;

        int matchedCount;

        for (int j = 2; j < pattern.length; j++) {

            // previously matched count
            matchedCount = next[j - 1];
            while (matchedCount != -1) {
                // Standing at index j, if previous char pattern[j-1] matches the (matchedCount)th char, current next[j] increases
                // And up till index j-1, next[j] chars matches

                // matched chars pattern[0:matchedCount-1]
                if (pattern[j - 1] == pattern[matchedCount]) {
                    next[j] = matchedCount + 1;

                    break;
                }

                // if not match, technically, we need to compare from the head, but we can take advantage of the previously
                // computed offset information. Consequently, set matchedCount to the offset that pattern failed to match
                // at (matchedCount)th char instead of starting over from the head. Take following pattern string as example,
                // 9th char is 'd' which differs from 5th char 'f', but we don't have to search from 6th char, we can take
                // advantage of next[4]=1, then compare 1th char 'd' with 9th char 'd'.

                // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                // [s, d, f, s, f, s, d, f, s, d, f]
                // [-1,0, 0, 0, 1, 0, 1, 2, 3, 4, 2]
                matchedCount = next[matchedCount];

                next[j] = 0;
            }
        }

        return next;
    }
}

Incorrect Solutions

class Solution {

    // FIXME Time limit exceeds. Actually the following idea is much more time consuming than the brute force.

    // This problem is not that difficult, the trick is to find the max length palindrome
    // starting from index 0

    public String shortestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        // find the max length palindrome starting from index 0
        int maxLen = 1;
        if (s.charAt(0) == s.charAt(1)) {
            maxLen = 2;
        }

        Set<String> validPal = new HashSet<>();
        Set<String> invalidPal = new HashSet<>();

        // ws is window size
        for (int ws = 1; ws <= s.length(); ws++) {
            for (int start = 0; start < s.length() - ws + 1; start++) {
                String sub = s.substring(start, start + ws);
                if (ws == 1) {
                    validPal.add(sub);

                    continue;
                }

                if (ws == 2) {
                    if (sub.charAt(0) == sub.charAt(1)) {
                        validPal.add(sub);
                    } else {
                        invalidPal.add(sub);
                    }

                    continue;
                }

                // for window size >= 3
                String subsub = sub.substring(1, ws - 1);

                // if the middle string is invalid
                if (invalidPal.contains(subsub)) {
                    invalidPal.add(sub);

                    continue;
                }

                if (sub.charAt(0) != sub.charAt(ws - 1)) {
                    invalidPal.add(sub);

                    continue;
                } else {
                    validPal.add(sub);

                    if (start == 0) {
                        maxLen = ws;
                    }
                }
            }
        }

        String ans = "";
        String prefix = s.substring(maxLen);
        for (int i = 0; i < prefix.length(); i++) {
            ans = prefix.charAt(i) + ans;
        }

        ans += s;

        return ans;
    }
}

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""