一个域名怎么用来做多个网站,凡科网干嘛的,南通通州区网站制作,租网络服务器多少钱题目描述
给你一个字符串 s#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。
示例 1#xff1a; 输入#xff1a;s “babad” 输出#xff1a;“bab” 解释#xff1a;“aba” 同样是符合题意的答案。 示…题目描述
给你一个字符串 s找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
示例 1 输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。 示例 2
输入s “cbbd” 输出“bb” 提示 1 s.length 1000 s 仅由数字和英文字母组成
解题思路
要找到最长的回文子串可以使用动态规划或中心扩展两种方法来解决。下面我将分别介绍这两种方法的思想并提供使用Scala编写的示例代码。
动态规划方法
动态规划的思想是利用已知的子问题的解来求解更大规模的问题的解。在这个问题中我们可以使用一个二维数组 dp其中 dp(i)(j) 表示从索引 i 到索引 j 的子串是否为回文串。状态转移方程如下
dp(i)(j) dp(i1)(j-1) s(i) s(j)在更新 dp 数组的过程中需要注意边界条件和更新顺序。
中心扩展方法
中心扩展的思想是以每个字符或两个字符之间的空隙作为回文串的中心然后向两边扩展来判断是否为回文串。具体步骤如下
从左到右遍历每个字符以当前字符为中心向两边扩展找到以当前字符为中心的最长回文子串。从左到右遍历每两个相邻字符之间的空隙以空隙为中心向两边扩展找到以空隙为中心的最长回文子串。
使用以上两种方法中的任何一种都可以解决这个问题。下面是使用Scala编写的示例代码演示了动态规划方法的实现
object Solution {def longestPalindrome(s: String): String {val n s.lengthvar start 0var maxLength 1val dp Array.ofDim[Boolean](n, n)for (i - 0 until n)dp(i)(i) truefor (length - 2 to n) {for (i - 0 until n - length 1) {val j i length - 1if (s(i) s(j)) {if (length 2 || dp(i 1)(j - 1)) {dp(i)(j) trueif (length maxLength) {maxLength lengthstart i}}}}}s.substring(start, start maxLength)}def main(args: Array[String]): Unit {val s1 babadval s2 cbbdprintln(longestPalindrome(s1)) // Output: babprintln(longestPalindrome(s2)) // Output: bb}
}
