给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。示例 2：
输入: “cbbd”
输出: “bb”蛮力法
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/**
* 蛮力法，O(n^3)
*/
def solution1(str: String): String = {
var i = 0
var max = 0
var res: String = ""
while (i < str.length) {
for (j <- i + 1 until str.length) {
if (isPalindrome(str.substring(i, j + 1))) {
if (str.substring(i, j + 1).length > max) {
res = str.substring(i, j + 1)
max = str.substring(i, j + 1).length
}
}
}
i += 1
}
res
}
def isPalindrome(str: String): Boolean = {
for (i <- 0 until str.length / 2) {
if (str.charAt(i) != str.charAt(str.length - i - 1)) {
return false
}
}
true
}中心扩散法
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/**
* 中心扩散法，O(n^2)
*/
def solution2(str: String): String = {
var max = 0
var res: String = ""
if (str.length == 1) {
return str
}
for (i <- 0 until str.length - 1) {
val str1 = expend(str, i, i)
val str2 = expend(str, i, i + 1)
val target = if (str1.length > str2.length) str1 else str2
if (target.length > max) {
res = target
max = target.length
}
}
res
}
def expend(str: String, i: Int, j: Int): String = {
var k = i
var l = j
while (k >= 0 && l < str.length && str.charAt(k) == str.charAt(l)) {
k -= 1
l += 1
}
str.substring(k + 1, l)
}