返回信息流语言的话用的是swift…
想使用动态规划解决，字符串为S
定义：如果S[i]和S[j]之间的字符串是回文的，则c[i,j] = 1，否则c[i,j] = 0
如果S[i]==S[j]，则c[i,j] = c[i-1,j+1]
如果S[i]==S[i+1], 则c[i,i+1] = 1
原始条件：c[i,i]=1
自己测试的话没有问题…超时难道是因为swift蛋疼的字符串操作吗…？求大神解答啊为什么会超时[em9]
下面贴代码…
func findLongestPalindrome(s: String) -> String{
var c = [[Bool]]() //记录中间结果的表
var begin = 0 //记录回文子串起始位置
var maxLen = 0 //记录回文子串长度
for _ in 0...s.characters.count { //给表赋初值false
c.append(Array(count:s.characters.count ,repeatedValue:false));
}
for var i = 0 ; i < s.characters.count ; i++ {
c[i][i] = true
begin = i
maxLen = 1
}
for var i = 0 ; i < s.characters.count - 1 ; i++ {
if s[s.startIndex.advancedBy(i)] == s[s.startIndex.advancedBy(i+1)]{ //判断s[i],s[i+1]是否相等
c[i][i+1] = true
begin = i
maxLen = 2
}
}
for var length = 3 ; length <= s.characters.count ; length++ {
for var i = 0; i < s.characters.count - length + 1; i++ {
let j = i + length - 1
if s[s.startIndex.advancedBy(i)] == s[s.startIndex.advancedBy(j)] && c[i+1][j-1]{ //判断s[i],s[j]是否相等
c[i][j] = true
begin = i
maxLen = length
}
}
}
let start = s.startIndex.advancedBy(begin); //截取字符串作为结果
let end = s.endIndex.advancedBy(-(s.characters.count - begin - maxLen));
let range = Range<String.Index>(start: start,end: end);
let result = s.substringWithRange(range);
return result
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #88908同步于 2016/2/22
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
求问Leetcode第5题，求一个字符串的最长回文子串，超时…
qgpmztmf
2016/2/22镜像同步20 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
第二个for循环判断包含两个元素的回文字符情况，但是貌似可以删除吧？和第三个for循环结合到一块不行么，就是第三个for循环lenth从2开始，第二个for循环删掉
第一个for循环，begin = i 这句也可以删掉吧？
最后几句看不懂，但感觉没问题，应该是能求出回文串，下标相差最大的就是最长回文串
【 在 jokenliv 的大作中提到: 】
: 第二个for循环判断包含两个元素的回文字符情况，但是貌似可以删除吧？和第三个for循环结合到一块不行么，就是第三个for循环lenth从2开始，第二个for循环删掉
: 第一个for循环，begin = i 这句也可以删掉吧？
: 最后几句看不懂，但感觉没问题，应该是能求出回文串，下标相差最大的就是最长回文串
老司机