Dynamic Programming

Published by powerfulyang on Jul 13, 2023

动态规划

Longest Palindromic Substring

最长回文子串

1function longestPalindrome(s: string): string {
2    if(s.length < 2){
3        return s;
4    }
5    let start = 0, maxLength = 1;
6    const dp: boolean[][] = Array.from(new Array(s.length), () => new Array(s.length).fill(false));
7    
8    for(let j = 0; j < s.length; j++){
9        for(let i = 0; i <= j; i++){
10            if(j - i < 2){
11                dp[i][j] = s[i] === s[j];
12            }else{
13                dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1];
14            }
15            
16            if(dp[i][j] && maxLength < j - i + 1){
17                maxLength = j - i + 1;
18                start = i;
19            }
20        }
21    }
22    return s.substring(start, start + maxLength);
23}

在这个解决方案中，我们用 dp[i][j] 表示子串 s[i...j] 是否为回文子串，然后根据状态转移方程去逐步填充 dp 数组，并在过程中记录最大的回文子串。最后，返回最长的回文子串。

这个解法的时间复杂度和空间复杂度都是 O(n^2)，其中 n 是字符串的长度。

typescript

1function longestPalindrome(s: string): string {
2    if (s.length < 2) {
3        return s;
4    }
5
6    let start = 0;
7    let end = 0;
8
9    const expandAroundCenter = (s: string, left: number, right: number) => {
10        while (left >= 0 && right < s.length && s[left] === s[right]) {
11            left--;
12            right++;
13        }
14
15        return right - left - 1;
16    }
17
18    for (let i = 0; i < s.length; i++) {
19        let len1 = expandAroundCenter(s, i, i);
20        let len2 = expandAroundCenter(s, i, i + 1);
21
22        let len = Math.max(len1, len2);
23        if (len > end - start) {
24            start = i - Math.floor((len - 1) / 2);
25            end = i + Math.floor(len / 2);
26        }
27    }
28
29    return s.substring(start, end + 1);
30}

这个函数通过遍历字符串中的每个字符，对每个字符进行"中心扩散"，找出以该字符为中心的最长回文子串。其中 expandAroundCenter 函数就是进行这个"中心扩散"的操作。最后，返回最长的回文子串。

注意，这个解法时间复杂度为 O(n^2)，空间复杂度为 O(1)。其中 n 是字符串的长度。如果字符串非常大，可能会有性能问题，那时就需要考虑其他更复杂的算法。

# Dynamic Programming

## Longest Palindromic Substring