首页 > 代码库 > LeetCode No.5 Longest Palindromic Substring
LeetCode No.5 Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
最长回文子串。
有两种思路：
1，从左向右找对称点，从对称点（或者两个相同的相邻字符）向两边搜索，记下搜到的最大长度。
2，设置一个二维bool数组，A[i, j] = TRUE 表示字符串中从i到j是回文串。
那么首先把所有A[i, i]设为TRUE（即长度为1，是回文），再线性找一遍看是否有相邻的相同字符（长度为2的回文），如有将A[i, i + 1]设为TRUE。
从长度为3开始，判断头尾，若头尾相同且A[i+1, j-1] == TRUE（即剩下的是回文），那么这个子串就是回文子串。
我采用的第二种方法。代码如下。
bool tab[1000][1000]; string longestPalindrome(string s) { string max; int n = s.size(); if (n == 0 || n == 1) return s; for (int i = 0; i < n; i++) tab[i][i] = true; for (int i = 0; i < n - 1; i++) { if (s[i] == s[i + 1]) { max = s.substr(i, 2); tab[i][i + 1] = true; } } for (int k = 3; k <= n; k++) { for (int i = 0; i < n - k + 1; i++) { int j = i + k - 1; if (tab[i + 1][j - 1] && s[i] == s[j]) { tab[i][j] = true; if (k > max.size()) max = s.substr(i, k); } } } return max; }
两种方法如果我没算错应该都是平方级别的复杂度。
不贴运行时间了，因为同样的代码提交两次时间差很多，没法说明问题。不过这个思路还是值得记录的。
LeetCode No.5 Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。