leetcode 05 回文字符串

1. 描述

給你一個字符串，找到里面最長的回文字符串

2. 事例

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。

示例 2：

輸入：s = "cbbd"
輸出："bb"

3. 思路

3.1 什么是回文字串

abba
abcba

我們把這種不管是從前到后讀還是從后到前讀都是一樣的單詞叫做回文字串

3.2 思路

3.2.1 dp數組

明確一個dp數組，即當前dp數組每個下標對應的含義

dp[i][j] 表示s的前i個字符到j個字符是否符合回文字串。

3.2.2 怎么判斷當前子串是回文字串。

$$
dp[i][j] = s[i] == s[j] and s[i+1][j-1] or j - 1 <= 2
$$

假設我現在有個字符串aba

當s[i]和s[j]等于當時候，我們就需要判斷從i到j里面包含了幾個字符。

比如當i = 0 j = 2當是時候，如果s[i] = s[j] 就只需要判斷里面的元素是否大于1了，我們就可以得到一個公式。
$$
j - i <= 2
$$

如果這個公式成立的話，并且s[i] = s[j] 那么就是一個回文字串。

只需要判斷s[i] == s[j] 并且 s[i + 1] [j - 1] 或者 j - i <= 2。

3.3.3 怎么取最大的回文字串。

我們上面知道了怎么判斷字串是回文字串，我們就可以先定義一個left，并記錄一個最大的長度。然后每次是回文字串的時候判斷是否大于已經記錄的，如果大于則就進行替換，如果小宇我們就跳過。

注意！！！ 這里我們要注意下。

這里的最大長度應該好似j - i + 1.

3.3.4 代碼編寫

3.3.4.1 python

def longestPalindrome(s: str) -> str:
    if len(s) <= 1:
        return s
    left = 0
    maxLength = 1
    dp = [[False for i in range(len(s))] for i in range(len(s))]
    for j in range(1, len(s)):
        for i in range(j):
            if s[i] != s[j]:
                continue
            else:
                dp[i][j] = dp[i + 1][j - 1] or j - i <= 2
            if dp[i][j] and j - i + 1 > maxLength:
                left = i
                maxLength = j - i + 1
    return s[left: left + maxLength]

3.3.4.2 typescript

onst longestPalindrome = (s: string): string => {
    if (s.length <= 1) return s;
    let left = 0, maxlength = 1;
    const dp = new Array(s.length).fill(0).map(item => new Array(s.length).fill(false));
    for (let j = 1; j < s.length; j++) {
        for (let i = 0; i < j; i++) {
            if (s[i] !== s[j]) continue;
            dp[i][j] = dp[i + 1][j - 1] || j - i <= 2;
            if (dp[i][j] && j - i + 1 > maxlength) {
                maxlength = j - i + 1;
                left = i;
            }
        }
    }
    return s.slice(left, left + maxlength)
}

java

 public static String longestPalindromeV2(String s) {
        int left = 0;
        int maxLength = 1;
        boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
        if (s.length() <= 1) return s;
        for (int j = 1; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) {
                    continue;
                } else {
                    dp[i][j] = dp[i + 1][j - 1] || j - i <= 2;
                }
                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    left = i;
                }
            }
        }
        return s.substring(left, left + maxLength);
    }