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

Example 1:

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

1
2

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

Constraints:

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

Solution

因為要找最大迴文子字串,而迴文字串前後讀法都一樣,意即可以將題目理解為若字串 s="babad 而將字串倒至則 reverse(s)="dabab,找到這兩個字串最大相同子字串,並且
要再正確的位置(相對倒至相同之位置).

Step 1. 如何找最大相同子字串?

if len(s1) = len(s2)

  • 將s1, s2組成二維矩陣
  • 比對矩陣對應字母是否相等
  • 找到最長標記相同對角線即為最大相同子字串

若 s1="acbcbcef", s2="abcbced", 則矩陣

-acbcbcef
a10000000
b00101000
c01010100
b00101000
c01010100
e00000010
d00000000

若要找長度,可在填寫矩陣時就先行計算加上左上較之值,即

1

arr[i][j] = 1 + arr[i-1][j-1]

則表格會是以下:

-acbcbcef
a10000000
b00101000
c01020200
b00203000
c01030400
e00000050
d00000000

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

pub fn longest_substring_length(str1: &str, str2: &str) -> usize {
    let len = str1.len();
    let mut max_len = 0;
    let mut arr: Vec<Vec<usize>> = vec![vec![0; len]; len];
    for (i, c1) in str1.chars().enumerate() {
        for (j, c2) in str2.chars().enumerate() {
            if c1 == c2 {
                if i == 0 || j == 0 {
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = 1 + arr[i - 1][j - 1];
                }
                max_len = max_len.max(arr[i][j])
            }
        }
    }
    max_len
}

Step 2. 匹配正確位置

首先,改寫上面function,回傳字串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

pub fn longest_palindrome(s: String) -> String {
    let len = s.len();
    let mut max_len = 0;
    let mut max_end = 0;
    let mut arr: Vec<Vec<usize>> = vec![vec![0; len]; len];
    for (i, c1) in s.chars().enumerate() {
        for (j, c2) in s.chars().rev().enumerate() {
            if c1 == c2 {
                if i == 0 || j == 0 {
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = 1 + arr[i - 1][j - 1];
                }
                if max_len < arr[i][j] {
                    max_len = arr[i][j];
                    max_end = i;
                }
            }
        }
    }
    (&s[max_end + 1 - max_len..max_end + 1]).to_string()
}

但就出現問題了,若s="123ab321", reverse(s)="123ba321, 會找到123, 321但
都不是答案. 所以要檢查現在的相同字串是不是原先的字串位置倒置而成. 因此, 先找到
在j位置原始的index org_index = len - 1 - j. 而 原始index加上現在子字串長度應
為i, 即org_index - 1 + arr[i][j] == i, 若不相同則不成立, 因此程式修改為:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

pub fn longest_palindrome(s: String) -> String {
    let len = s.len();
    let mut max_len = 0;
    let mut max_end = 0;
    let mut arr: Vec<Vec<usize>> = vec![vec![0; len]; len];
    for (i, c1) in s.chars().enumerate() {
        for (j, c2) in s.chars().rev().enumerate() {
            if c1 == c2 {
                if i == 0 || j == 0 {
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = 1 + arr[i - 1][j - 1];
                }
                if max_len < arr[i][j] {
                    if len - 1 - j + arr[i][j] - 1 == i {
                        max_len = arr[i][j];
                        max_end = i;
                    }
                }
            }
        }
    }
    (&s[max_end + 1 - max_len..max_end + 1]).to_string()
}

Time, Space Complexity: O(n^2)

TODO: other solution

Reference