国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 【Leetcode】Longest Palindromic Substring

【Leetcode】Longest Palindromic Substring

来源:程序员人生   发布时间:2016-06-24 17:32:38 阅读次数:2249次

题目链接: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); }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生