leetcode-5-Longest-Palindromic-Substring

发表于   |  

描述

Given a string s, return the longest palindromic substring in s.

Example 1:

1
2
3
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: s = "cbbd"
Output: "bb"

Example 3:

1
2
Input: s = "a"
Output: "a"

Example 4:

1
2
Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

分析

找字符串中最长的回文字符串。动态规划算法。dp[i][j] 为 true，表示 s[i:j] 是一个回文字符串，则有推导公式：
dp[i][j] = dp[i+1][j-1] (s[i] == s[j])
边界情况是：dp[i][i] = true, dp[i][i+1] = true (s[i]==s[i+1])

解决方案1(Python)

代码会超时。

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
class Solution:
    def longestPalindrome(self, s: str) -> str:
        sLen = len(s)
        if sLen < 2:
            return s
        
        maxLen = 1
        begin = 0
        dp = [[False] * sLen for _ in range(sLen)]
        for i in range(sLen):
            dp[i][i] = True
            
        for length in range(2, sLen+1):
            for left in range(sLen):
                right = length + left - 1
                if right >= sLen:
                    break
                    
                if s[left] != s[right]:
                    dp[left][right] = False
                else:
                    if right - left < 3:
                        dp[left][right] = True
                    else:
                        dp[left][right] = dp[left+1][right-1]
                if dp[left][right] and right-left+1 > maxLen:
                    maxLen = right - left + 1
                    begin = left
        return s[begin: begin+maxLen]

解决方案2(C++)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int sLen = s.size();
        if (sLen < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        vector<vector<int>> dp(sLen, vector<int>(sLen));
        for (int i = 0; i < sLen; i++) {
            dp[i][i] = true;
        }
        
        for (int length = 2; length <= sLen; length++) {
            for (int left = 0; left < sLen; left++) {
                int right = left + length - 1;
                if (right >= sLen) {
                    break;
                }

                if (s[left] != s[right]) {
                    dp[left][right] = false;
                } else {
                    if (right - left < 3) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }

                if (dp[left][right] && right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    begin = left;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

解决方案3（Golang）

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
30
func longestPalindrome(s string) string {
    var result string
    var sLen = len(s)
    var dp = make([][]int, sLen)
    
    for i, _ := range dp {
        dp[i] = make([]int, sLen)
    }
    
    for i := 0; i < sLen; i++ {
        for left := 0; left+i < sLen; left++ {
            right := left + i
            if i == 0 {
                dp[left][right] = 1
            } else if i == 1 {
                if s[right] == s[left] {
                    dp[left][right] = 1
                }
            } else {
                if s[right] == s[left] {
                    dp[left][right] = dp[left+1][right-1]
                }
            }
            if dp[left][right] == 1 && i + 1 > len(result) {
                result = s[left: right+1]
            }
        }
    }
    return result
}

相关问题

题目来源