最长回文子串golang

最长回文子串：动态规划解法

回文串是指正读和反读都一样的字符串，而回文子串则指在一个字符串中连续的部分也是回文串。在字符串处理中，求解最长回文子串是常见且重要的问题。本文将介绍一种使用动态规划的方法来解决最长回文子串问题。

对于一个字符串s，假设其长度为n，我们可以用一个二维数组dp表示s[i:j]是否为回文串，其中i和j分别表示字符串的起始位置和结束位置。当i等于j时，表示只有一个字符，一定是回文串，所以dp[i][j] = true。当i小于j时，我们需要比较s[i]和s[j]是否相等。如果相等，则它们是否是回文串依赖于s[i+1:j-1]，即dp[i+1][j-1]。如果不相等，则s[i:j]一定不是回文串，即dp[i][j] = false。

动态规划递推公式

根据以上分析，我们可以得到动态规划的递推公式：

dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

使用这个递推公式，我们可以依次计算出dp数组的值，并记录最长回文子串的起始位置和长度。

实现代码

``` func longestPalindrome(s string) string { n := len(s) if n < 2 { return s } dp := make([][]bool, n) for i := 0; i < n; i++ { dp[i] = make([]bool, n) dp[i][i] = true } start, maxLen := 0, 1 for j := 1; j < n; j++ { for i := 0; i < j; i++ { if s[i] == s[j] { if j-i < 3 { dp[i][j] = true } else { dp[i][j] = dp[i+1][j-1] } } else { dp[i][j] = false } if dp[i][j] && j-i+1 > maxLen { maxLen = j - i + 1 start = i } } } return s[start : start+maxLen] } ```

在上述代码中，我们首先检查字符串的长度，如果其长度小于2，直接返回原字符串。然后创建一个二维数组dp，并将长度为1的所有子串都标记为回文串。

接下来，我们使用两层循环来计算dp数组的值。在每次循环过程中，我们通过比较s[i]和s[j]来决定是否将dp[i][j]标记为回文串。同时，我们还会更新最长回文子串的起始位置和长度。

测试案例

``` func main() { testCases := []struct { str string want string }{ {"babad", "bab"}, {"cbbd", "bb"}, {"a", "a"}, {"ac", "a"}, } for _, testCase := range testCases { got := longestPalindrome(testCase.str) if got != testCase.want { fmt.Printf("Error: input = %s, want = %s, got = %s\n", testCase.str, testCase.want, got) } } } ```

以上代码是一个简单的测试案例，在实际使用时，我们可以根据具体需求编写更全面的测试案例。运行测试程序可以验证我们的实现是否能正确地找到最长回文子串。

总结

通过动态规划的方法，我们可以高效地解决最长回文子串问题。该算法的时间复杂度为O(n^2)，其中n是字符串的长度。相比于暴力枚举的方法，动态规划的算法效率更高。

当然，除了动态规划，还有其他方法可以用来解决最长回文子串问题，比如中心扩展法、Manacher's算法等。不同的方法适用于不同的场景，选择合适的解决方案可以提高代码的效率。

希望本文能够对你理解最长回文子串的求解方法有所帮助，并且能够在实际开发中发挥作用。