首页 > 代码库 > leetcode5。Longest Palindromic Substring
leetcode5。Longest Palindromic Substring
写了一个爆搜，超时了，所以更改了一个方法，使用flag数组记录标志，
动态规划，类似于lcs的解法，数组flag[i][j]记录s从i到j是不是回文
首先初始化，i>=j时，flag[i][j]=true，这是因为s[i][i]是单字符的回文，当i>j时，为true，是因为有可能出现flag[2][1]这种情况，比如bcaa，当计算s从2到3的时候，s[2]==s[3]，这时就要计算s[2+1] ?= s[3-1]，总的来说，当i>j时置为true，就是为了考虑j=i+1这种情况。
接着比较s[i] = s[j]，如果成立，那么flag[i][j] = flag[i+1][j-1]，否则直接flag[i][j]=false
public class Solution { public String longestPalindrome(String s) { int n = s.length(); int max = 0,st = 0,end = 0; boolean [][]flag = new boolean[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(i < j) flag[i][j] = false; else flag[i][j] = true; } } for(int i = 1; i < n;i++) { for(int j = 0; j < i; j++ ) { if(s.charAt(i) == s.charAt(j)) { flag[j][i] = flag[j+1][i-1]; if(flag[j][i] == true && i - j + 1 > max) { max = i-j+1; st = j; end = i; } } else flag[j][i] = false; } } return s.substring(st,end+1); }}
不知怎么的，leetcode上提交第一次的时候，又是显示超时，但是又提交了一次后，显示通过了。（meng）。
leetcode5。Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。