【Leetcode】Longest Palindromic Substring

题目链接:https://leetcode.com/problems/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.

思路:

遍历该字符串每个位置,并判断以该位置为中位点的最长回文串的长度,复杂度为O(n^2)。 要注意如果回文串是奇数长度和偶数长度不同。所以需要遍历判断两次。1次默许该点为中心的回文串是奇数长,1次默许是偶数长。

算法:

public String longestPalindrome(String s) {
if (s.length() <= 1) {
return s;
}
if (s.length() == 2) {
if (s.charAt(0) == s.charAt(1)) {
return s;
} else {
return s.charAt(0) + "";
}
}

String res = "";
int maxLen = 0;
// 对奇位点判断
for (int i = 1; i < s.length() – 1; i++) {
String str = calPalin(s, i – 1, i + 1);
if (maxLen < str.length()) {
maxLen = str.length();
res = str;
}
}

// 对偶位点判断
for (int i = 1; i < s.length(); i++) {
String str = calPalin(s, i – 1, i);
if (maxLen < str.length()) {
maxLen = str.length();
res = str;
}
}

return res;
}

public String calPalin(String s, int left, int right) {
if (left < 0 && right >= s.length()) {
return "";
}
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left–;
right++;
}
return s.substring(left + 1, right);
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【Leetcode】Longest Palindromic Substring

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡