214. Shortest Palindrome

发表于 | 更新于: | 分类于 | 本文总阅读量 次
| 字数统计: 971 | 阅读时长 ≈ 6
  • 23.5%

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

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.

1
2
3
4
5
For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

此处需要思考

https://discuss.leetcode.com/topic/14526/c-8-ms-kmp-based-o-n-time-o-n-memory-solution

C++ 8 ms KMP-based O(n) time & O(n) memory solution

We can construct the following string and run KMP algorithm on it:

(s) + (some symbol not present in s) + (reversed string)

After running KMP on that string as result we get a vector p with values of a prefix function for each character (for definition of a prefix function see KMP algorithm description). We are only interested in the last value because it shows us the largest suffix of the reversed string that matches the prefix of the original string. So basically all we left to do is to add the first k characters of the reversed string to the original string, where k is a difference between original string size and the prefix function for the last character of a constructed string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string shortestPalindrome(string s) {
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        string l = s + "#" + rev_s;
        
        vector<int> p(l.size(), 0);
        for (int i = 1; i < l.size(); i++) {
            int j = p[i - 1];
            while (j > 0 && l[i] != l[j])
                j = p[j - 1];
            p[i] = (j += l[i] == l[j]);
        }
        
        return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
    }
};

https://discuss.leetcode.com/topic/14770/my-easily-understandable-but-time-consuming-c-solution

My easily understandable but time consuming C++ solution

The key idea is to first reverse the string, then check the max length from n to 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string shortestPalindrome(string s) {
        string s2=s;
        reverse(s2.begin(),s2.end());
        int n=s.size(),l;
        for(l=n;l>=0;l--)
        {
            if(s.substr(0,l)==s2.substr(n-l))
                break;
        }
        return s2.substr(0,n-l)+s;
    }
};

https://discuss.leetcode.com/topic/16275/accepted-4ms-c-solution-different-with-kmp-based-solution-and-easy-understand/2

Accepted 4ms c++ solution, different with KMP-based solution and easy understand.

For this problem, KMP-based solution is a very typical and classic O(n) solution. Here is a different solution, it’s also O(n), and I think it is more easy to understand.

In order to slove this problem, the key is to get the length of the longest palindromic prefix substring. if the length of s is len, and the length of the longest palindromic prefix substring is longest, the remaining substring will be s.substr(longest, len - longest), than we should reverse the remaining substring and adding it in front of s.

For example, if s is “abacbbcda”, so the longest palindromic prefix substring is “aba”(not “cbbc” because it’s not prefix string), and the remaining substring is “cbbcda”, we reverse the remaining substring and get “adcbbc”, so the result is “adcbbc” + “abacbbcda”.

The follow is my c++ solution, only 4ms. Please note that the condition in for loop is begin <= len / 2 instead of begin < len, because if begin > len / 2, the substring can not be prefix string, so there is no need to continue.

Update: I made wrong analysis, the complexity is O(N^2) but not O(N). Thanks very much for Sammax’s reminder.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    std::string shortestPalindrome(std::string s) {
		int len = s.length();
		if (len < 2)
			return s;
		// calculate the length of the longest palindromic prefix substring.
		int longest = 1, start, end;
		for (int begin = 0; begin <= len / 2;) {
			start = end = begin;
			while (end < len - 1 && s[end + 1] == s[end])
				++end;
			begin = end + 1;
			while (end < len - 1 && start > 0 && s[end + 1] == s[start - 1]) {
				++end;
				--start;
			}
			// start == 0 means the palindromic substring is also prefix string.
			if (start == 0 && longest < end - start + 1)
				longest = end - start + 1;
		}
		// reverse the remaining substring and adding it in front of s.
		std::string remaining = s.substr(longest, len - longest);
		std::reverse(remaining.begin(), remaining.end());
		return remaining + s;
    }
};

262ms, 29.90%, October 14, 2016

https://discuss.leetcode.com/topic/14542/ac-in-288-ms-simple-brute-force

AC in 288 ms, simple brute force

1
2
3
4
5
def shortestPalindrome(self, s):
    r = s[::-1]
    for i in range(len(s) + 1):
        if s.startswith(r[i:]):
            return r[:i] + s

Example: s = dedcba. Then r = abcded and I try these overlays (the part in (…) is the prefix I cut off, I just include it in the display for better understanding):

1
2
3
4
5
s          dedcba
r[0:]      abcded    Nope...
r[1:]   (a)bcded     Nope...
r[2:]  (ab)cded      Nope...
r[3:] (abc)ded       Yes! Return abc + dedcba

7ms, 69.02%, October 14, 2016

https://discuss.leetcode.com/topic/21068/my-7-lines-recursive-java-solution

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public String shortestPalindrome(String s) {
        int j = 0;
        for(int i = s.length() - 1; i>=0; i--){
            if(s.charAt(i) == s.charAt(j))
                j += 1;
        }
        if(j == s.length()) return s;
        String suffix = s.substring(j);
        return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0,j)) + suffix;
    }
}
谢谢你，可爱的朋友。