算法每日一练 (24)

💢欢迎来到张翊尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

文章目录

算法每日一练 (24)
- 最长回文子串
- - 题目描述
  - 解题思路
  - 解题代码
  - - `c/c++`
    - `golang`
    - `lua`

官方站点：力扣 Leetcode

算法每日一练 (24)

最长回文子串

题目地址：最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

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

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解题思路

本题目采用动态规划思想来解决。

有更优的解法，感兴趣的小伙伴可以自行查阅。

对于最长回文子串问题，可以定义一个二维数组 dp，其中 dp[i][j] 表示字符串从索引 i 到索引 j 的子串是否是回文。
在计算过程中，需要记录最长回文子串的起始位置和长度。为此定义两个变量：
- start：记录最长回文子串的起始索引。
- maxLen：记录最长回文子串的长度。
动态规划表 dp 的大小为 n × n，其中 n 是字符串的长度。初始化 dp 数组：
- 任何单个字符都是回文，因此对于所有的 i，dp[i][i] = 1。
- 如果两个连续字符相同，那么它们组成的子串也是回文。因此，如果 s[i] == s[i+1]，则 dp[i][i+1] = 1。
对于长度大于 2 的子串，需要通过状态转移来判断它们是否是回文。状态转移的核心思想是：
- 如果子串的首尾字符相同，并且去掉首尾字符后的子串也是回文，那么当前子串就是回文。

$\&\& dp[i+1][j-1])$

为了确保在计算 dp[i][j] 时，dp[i+1][j-1] 已经被计算过，故需要按照子串长度从小到大的顺序进行遍历。
在循环中根据上述的状态转移方程更新 dp 数组，并对 start 和 maxLen 依次更新。
最终返回 s 根据 start 和 maxLen 的子串即可。

解题代码

`c/c++`

#include <vector>class Solution
{
public:std::string longestPalindrome(std::string s){int sz = s.size();if (sz == 1)return s;std::vector<std::vector<int>> dp(sz, std::vector<int>(sz));int start = 0;int maxLen = 1;for (int i = 0; i < sz; i++)dp[i][i] = 1;for (int i = 0; i < sz - 1; i++){if (s[i] == s[i + 1]){dp[i][i + 1] = 1;start = i;maxLen = 2;}}for (int i = 3; i <= sz; i++){for (int j = 0; j < sz - i + 1; j++){int e = j + i - 1;if (s[j] == s[e] && dp[j + 1][e - 1] == 1){dp[j][e] = 1;start = j;maxLen = i;}}}return s.substr(start, maxLen);}
};

`golang`

func longestPalindrome(s string) string {sz := len(s)if sz == 1 {return s}start, maxLen := 0, 1dp := make([][]int, sz)for i := 0; i < sz; i++ {dp[i] = make([]int, sz)dp[i][i] = 1}for i := 0; i < sz-1; i++ {if s[i] == s[i+1] {dp[i][i+1] = 1start = imaxLen = 2}}for i := 3; i <= sz; i++ {for j := 0; j < sz-i+1; j++ {e := j + i - 1if s[j] == s[e] && dp[j+1][e-1] == 1 {dp[j][e] = 1start = jmaxLen = i}}}return s[start : start+maxLen]
}

`lua`

local function longestPalindrome(s)local sz = #sif sz == 1 thenreturn sendlocal start = 1local maxLen = 1local dp = {}for i = 1, sz dodp[i] = {}dp[i][i] = 1endfor i = 1, sz - 1 doif string.sub(s, i, i) == string.sub(s, i + 1, i + 1) thendp[i][i + 1] = 1start = imaxLen = 2endendfor i = 3, sz dofor j = 1, sz - i + 1 dolocal e = j + i - 1if string.sub(s, j, j) == string.sub(s, e, e) and dp[j + 1][e - 1] == 1 thendp[j][e] = 1start = jmaxLen = iendendendreturn string.sub(s, start, start + maxLen - 1)
end