东莞网站建设 钢结构,广州购物网站,同步手机wordpress,试用体验网站给定一个字符串 s#xff0c;找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1#xff1a; 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。
示例 2#xff1a; 输入: “cbbd” 输出: “bb”
本算法采用 动态规划去解析
func longes…给定一个字符串 s找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。
示例 2 输入: “cbbd” 输出: “bb”
本算法采用 动态规划去解析
func longestPalindrome(s string) string {n :len(s)dp :make([][]int,n)for i:0;in;i{dp[i] make([]int,n)}ans : for k:0;kn;k{for i:0;ikn;i{j:ikif k 0 {dp[i][j] 1}else if k 1 {if s[i] s[j] {dp[i][j] 1}}else {if s[i] s[j] {dp[i][j] dp[i1][j-1]} }if dp[i][j] 1 k1 len(ans){ans s[i:j1]}}}return ans
}
代码解析
初始化二维 DP 表格 n : len(s)
dp : make([][]int, n)
for i : 0; i n; i {dp[i] make([]int, n)
}
功能
dp[i][j] 表示子串 s[i:j1] 是否是回文子串。值为 1 表示是回文0 表示不是。 初始化一个大小为 n × n 的二维数组 dp用于存储所有子串的回文状态。 2. 遍历子串长度 k主循环
for k : 0; k n; k {for i : 0; ik n; i {j : i k...}
}
功能
遍历所有可能的子串长度 kk1 是实际长度。 i 是子串的起始位置j i k 是子串的结束位置。 子串的范围是 s[i:j1]。 3. 判断子串是否是回文
if k 0 {dp[i][j] 1
} else if k 1 {if s[i] s[j] {dp[i][j] 1}
} else {if s[i] s[j] {dp[i][j] dp[i1][j-1]}
}
功能
根据子串长度的不同情况判断是否为回文 长度为 1k 0 单个字符总是回文直接标记为 1。 长度为 2k 1 如果两个字符相等则是回文。 长度大于 2k 1 首尾字符相等且去掉首尾的子串 s[i1:j] 也为回文通过 dp[i1][j-1] 判断。
更新答案
if dp[i][j] 1 k1 len(ans) {ans s[i : j1]
}
功能
如果当前子串 s[i:j1] 是回文且长度超过当前记录的最长回文则更新答案 ans。 k1 是子串的实际长度。
完整运行流程示例 假设输入字符串为 s “babad”
初始化 dp 矩阵为全 0ans “”。 遍历所有可能的子串 子串长度 k 0 每个单字符都是回文如 dp[0][0] 1dp[1][1] 1。 子串长度 k 1 检查相邻字符是否相等。如 s[0:2] “ba” 不是回文但 s[1:3] “aba” 是回文。 子串长度 k 2 检查三字符回文通过 dp[i1][j-1] 判断。 每次找到更长的回文时更新答案。 最终结果为 “bab” 或 “aba”。
复杂度分析 时间复杂度O(n²) 遍历子串的起点 i 和长度 k。 空间复杂度O(n²) 使用了一个二维数组 dp 存储状态。
