LeetCode 5. Longest Palindromic Substring
2020-05-30 08:01:50 # leetcode # dynamic programming # string

Problem

LeetCode 5. Longest Palindromic Substring

1. 题目简述

找出一个字符串的最长回文子字符串。例如：

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

2. 算法思路

一道经典老题目了，也不分析了，直接背答案吧，和它相似的题目还有两道，“LeetCode 516 最长回文子序列”和“LeetCode 647 回文子字符串”。

Dynamic Programming

首先，对于这种求最值的问题，第一反应就应该是DP，确实这道题是一个经典的斜着DP的题目。

我们定义dp[i][j]表示从index为i到j的子字符串是否是回文序列。

base case是当i == j时，dp[i][j] = true；对于其他的任意一对i和j，如果s[i]和s[j]相同，则只要dp[i + 1][j - 1]为true，dp[i][j]就为true，或者 j - i <= 2 也可满足要求，若 j-i == 1，则是两个相邻的字符，类似于“aa”；如果j - i == 2，则有可能是“aba”这种类型的字符串，也是回文字符串。故有如下递推式

\begin{equation}
dp[i][j] = dp[i + 1][j - 1] || j - i \leq 2 \text{ if } s[i] = s[j]
\end{equation}

\begin{equation}
dp[i][j] = false \text{ if } s[i] \neq s[j]
\end{equation}

遍历顺序根据自身喜好来，注意j是要大于i的，所以整张dp表只有一半会被遍历到。而且要注意，当计算dp[i][j]的时候，dp[i + 1][j - 1]必须是已经计算完毕的了，因此建议i从后向前计算，也就是从n - 1开始，到0。然后每次j从i + 1到n - 1.

时间复杂度为O(n ^ 2)，空间复杂度也是O(n ^ 2)

中心扩散法

对于每个回文序列来说，它的特性是镜像对称的，也就是说它存在一个中心点（长度为奇数）或者中轴（长度为偶数）。

对于0到n - 1中任意一个字符i，它可能是中心点，也可能是在某中轴的左右侧。如果他是中心点，那么从i分别向左右扩散，会找到以i为中心的回文子串，直到两端或者不匹配；如果中轴刚好在它的右侧，那么从i向左和i+1向右出发（包括i和i+1），逐渐找到回文字符串。

3. 解法

Dynamic Programming bottom-up

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

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }

        int n = s.length(), longest = 0, start = 0, end = 0;
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && ((dp[i + 1][j - 1]) || (j - i <= 2))) {
                    dp[i][j] = true;
                    if (j - i + 1 > longest) {
                        start = i;
                        end = j;
                        longest = j - i + 1;
                    }
                }
            }
        }

        return s.substring(start, end + 1);
    }
}

中心扩散法

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
28
29
public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }

        int longest = 0, start = 0;

        for (int i = 0; i < s.length(); i++) {
            int currentLongest = Math.max(findPalindrome(s, i, i),findPalindrome(s, i, i + 1));
            if (currentLongest > longest) {
                longest = currentLongest;
                start = i - (longest - 1)/ 2;
            }
        }

        return s.substring(start, start + longest);

    }

    private int findPalindrome(String s, int l, int r) {
        while (l >=0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

Prev
2020-05-30 08:01:50 # leetcode # dynamic programming # string
Next