leetcode5：最长回文子串

链接

leetcode

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    双指针

    由于字符串长度小于 1000，所以可以使用 O(n^2) 的算法枚举所有可能的情况。
    枚举回文串的中心 i，然后分两种情况向两边扩展，直到遇到不同字符为止:
        1.若回文串长度为奇数，则依次判断 s[i−k] == s[i+k], k = 1, 2, 3, ...
        2.若回文串长度为偶数，则依次判断 s[i−k] == s[i+k−1], k = 1, 2, 3, ...
    遇到不同字符时，就找到了以 i 为中心的回文串边界。

    时间复杂度：O(n^2)
        其中 n 是字符串的长度。
    空间复杂度：O(1)
*/
class Solution_0 {
public:
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i < s.size(); i++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) {
                l--, r++;
            }
            if (res.size() < r - l - 1) {
                res = s.substr(l + 1, r - l - 1);
            }

            l = i, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) {
                l--, r++;
            }
            if (res.size() < r - l - 1) {
                res = s.substr(l + 1, r - l - 1); 
            }
        }

        return res;
    }
};

/* 
    思路同上
*/
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i < s.size(); i++) {
            // 长度为奇数，以 s[i] 为中心的最长回文子串
            string s1 = check(s, i, i);
            // 长度为偶数，以 s[i] 和 s[i + 1] 为中心的最长回文子串
            string s2 = check(s, i, i + 1);
            res = res.size() > s1.size() ? res : s1;
            res = res.size() > s2.size() ? res : s2;
        }

        return res;
    }

    string check(const string& s, int l, int r) {
        // 防止下标越界，向两侧扩展
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--, r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substr(l + 1, r - l - 1);
    }
};

/*
    状态表示：
        f[i][j] 表示 s[i...j] 是否为回文串
    状态计算：
        f[i][j] = s[i-1] == s[j-1] && (j-i < 2 || f[i+1][j-1])

    时间复杂度：O(n^2)
    空间复杂度：O(n^2)
*/
class Solution_2 {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));

        int start = -1, length = 0;
        for (int i = n; i >= 1; i--) {
            for (int j = i; j <= n; j++) {
                f[i][j] = s[i-1] == s[j-1] && (j - i < 2 || f[i+1][j-1]);
                if (f[i][j] != 0 && length < j - i + 1) {
                    start = i;
                    length = j - i + 1;
                }
            }
        }
        return s.substr(start - 1, length);
    }
};

/*
    思路同上，正向遍历
*/
class Solution_3 {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));

        int start = 0, length = 0;
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int l = i, r = i + len - 1;
                if (len == 1) {
                    f[l][r] = 1;
                } else if (len == 2) {
                    f[l][r] = (s[l] == s[r]);
                } else {
                    f[l][r] = f[l+1][r-1] && (s[l] == s[r]);
                }
                if (f[l][r] != 0 && length < r - l + 1) {
                    start = l;
                    length = r - l + 1;
                }
            }
        }
        return s.substr(start, length);
    }
};

int main() {
    vector<string> test_cases = { "babad", "cbbd" };

    for (auto s : test_cases) {
        Solution solution;
        cout << "Input: " << s << endl;
        string result = solution.longestPalindrome(s);
        cout << "Output: " << result << endl;
    }

    return 0;
}

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
// 5. 最长回文子串
// 高频面试题 - CodeTop

package main

import (
	"fmt"
)

// contains 检查 result 是否在 expected 列表中
func contains(expected []string, result string) bool {
	for _, exp := range expected {
		if exp == result {
			return true
		}
	}
	return false
}

/*
	暴力解法
	枚举所有可能的子串，并检查每个子串是否为回文，最终返回最长的回文子串。
		
	时间复杂度：O(n^3)
	空间复杂度：O(1)
*/
func longestPalindrome_0(s string) string {
    maxLen := 0
	longest := ""

	// 枚举所有可能的子串
	for i := 0; i < len(s); i++ {
		for j := i + 1; j <= len(s); j++ {
			substr := s[i:j] // 当前子串
			if isPalindrome(substr) && len(substr) > maxLen {
				maxLen = len(substr)
				longest = substr
			}
		}
	}
	return longest
}

// isPalindrome 检查一个字符串是否为回文
func isPalindrome(s string) bool {
    for i := 0; i < len(s)/2; i++ {
        if s[i] != s[len(s)-1-i] {
            return false
        }
    }
    return true
}

/*
	左右指针从中心向两端扩展。

    时间复杂度：O(n^2)
        其中 n 是字符串的长度。
    空间复杂度：O(1)
*/
func longestPalindrome(s string) string {
    var res string
    for i := 0; i < len(s); i++ {
        // 以 s[i] 为中心的最长回文子串
        s1 := getPalindromeStr(s, i, i)
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        s2 := getPalindromeStr(s, i, i + 1)
        if len(res) < len(s1) {
            res = s1
        }
        if len(res) < len(s2) {
            res = s2
        }
    }
    return res
}

func getPalindromeStr(s string, l, r int) string {
    // 防止索引越界，找到回文串所在的区间
    for l >= 0 && r < len(s) && s[l] == s[r] {
        l--
        r++
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s[l+1:r]
}

/*
   动态规划：
		使用二维数组 dp[i][j] 表示子串 s[i:j+1] 是否是回文串。
		初始化单个字符为回文串：dp[i][i] = true。
		检查长度为 2 的子串，如果两个字符相同，则为回文串。
		检查长度大于 2 的子串，状态转移方程为：
			dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]。
   边界条件：
       如果字符串为空，返回空字符串。

   时间复杂度：O(n^2)
       遍历所有可能的子串，时间复杂度为 O(n^2)，其中 n 是字符串的长度。
   空间复杂度：O(n^2)
       使用了一个大小为 n*n 的二维数组 dp，空间复杂度为 O(n^2)。
*/
// longestPalindrome 返回最长的回文子串
func longestPalindrome_2(s string) string {
	n := len(s)
	if n == 0 {
		return ""
	}

	// dp[i][j] 表示 s[i:j+1] 是否是回文串
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	// 初始化单个字符为回文串
	for i := 0; i < n; i ++ {
		dp[i][i] = true
	}

	start, maxLen := 0, 1
	// 从后向前遍历
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			// 比较当前两个字符
			if s[i] == s[j] {
				if j - i == 1 {
					// 长度为 2 的子串
					dp[i][j] = true
				} else {
					// 长度大于 2 的子串
					dp[i][j] = dp[i+1][j-1]
				}
				// 更新最长回文子串
				if dp[i][j] && j-i+1 > maxLen {
					start = i
					maxLen = j-i+1
				}
			}
		}
	}
	return s[start:start+maxLen]
}

/*
    思路同上，正向遍历
*/
func longestPalindrome_3(s string) string {
	n := len(s)
	if n == 0 {
		return ""
	}

	// dp[i][j] 表示 s[i:j+1] 是否是回文串
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	// 初始化单个字符为回文串
	for i := 0; i < n; i ++ {
		dp[i][i] = true
	}

	start, maxLen := 0, 1
	// 正向遍历，计算所有子串
	for length := 2; length <= n; length++ {
		// 子串起始位置
		for i := 0; i <= n - length; i++ {
			j := i + length - 1 // 子串结束位置
			if s[i] == s[j] {
				if length == 2 || dp[i+1][j-1] {
					dp[i][j] = true
					if length > maxLen {
						start = i
						maxLen = length
					}
				}
			}
		}
	}
	return s[start:start+maxLen]
}

func main() {
	// 测试用例
	testCases := []struct {
		s        string
		expected []string
	}{
		{
			s:        "babad",
			expected: []string{"bab", "aba"},
		},
		{
			s:        "cbbd",
            expected: []string{"bb"},
		},
	}

	for i, tc := range testCases {
		result := longestPalindrome(tc.s)
		fmt.Printf("Test Case %d, Input: s = %q\n", i+1, tc.s)

        if contains(tc.expected, result) {
			fmt.Printf("Test Case %d, Output: %q, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %q, FAIL (Expected: %q)\n", i+1, result, tc.expected)
		}
	}
}
#leetcode
leetcode5：最长回文子串
https://lcf163.github.io/2023/08/10/leetcode5：最长回文子串/
作者
乘风的小站
发布于
2023年8月10日
许可协议