LeetCode-Longest Palindromic Substring
原创
LeetCode-Longest Palindromic Substring
原创
卡尔曼和玻尔兹曼谁曼
发布于 2019-02-10 05:30:39
发布于 2019-02-10 05:30:39
版权声明：本文为博主原创文章，转载请注明原文出处！
写作时间：2019-02-10 00:04:34
LeetCode-Longest Palindromic Substring
题目描述
LeetCode第5道题目：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.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.Example 2:
Input: "cbbd"
Output: "bb"题目要求我们找到给定字符串中的所有回文子串中最长子串。
思路分析
这个题目和之前的LeetCode-Palindromic Substrings题目的思路是一样的，Palindromic Substrings是找回文的个数。在这个过程中其实我们是找出了所有的回文子串，接下来我们统计一下每个回文的长度，选择出最长的那个就是本文的答案了（当然，在代码实现过程中统计最长子串不一定是找到了所有的子串之后再统计，可能是边寻找边统计）。所以，方法还是老方法，可以利用动态规划，也可以利用中心扩散法。
有不明白的地方可以参见我之前的博文《LeetCode-Palindromic Substrings》，这里我只给出了使用中心扩散法进行求解的代码实现。
C++实现
class Solution {
private:
int longest = 0; // 记录最长子串的字符个数
string palindrome = ""; // 保存最长的子串
void extendPalindrome(const string& s, int left, int right) {
while ((left >= 0) && (right < s.size()) && (s[left] == s[right])) {
--left;
++right;
}
int count = right - left - 1;
if (count > longest) {
longest = count;
palindrome = s.substr(left + 1, longest);
}
}
public:
string longestPalindrome(string s) {
for (int i = 0; i < s.size(); ++i) {
extendPalindrome(s, i, i);
extendPalindrome(s, i, i + 1);
}
return palindrome;
}
};可以对比一下，和LeetCode-Palindromic Substrings的答案是不是没多大变化？
Scala实现
object Solution {
def longestPalindrome(s: String): String = {
s.length match {
case 0 => s
case _ => {
val longest = (for {
i <- s.indices
j <- List(i, i + 1)
k <- (i to 0 by -1).zip(j until s.length).takeWhile(p => s(p._1) == s(p._2))
} yield (k._1, k._2)).maxBy(p => p._2 - p._1)
s.substring(longest._1, longest._2 + 1)
}
}
}
}这里需要注意的是：
- 需要对于空字符串的特殊处理（这里使用的是
match匹配，当然也可以使用if...else条件语句） - 我们使用
yield每次生成回文子串的左右指针，然后再使用maxBy得到最长子串对应的左右指针。 takeWhile函数对集合进行遍历过程中当条件不满足的时候会立即停止判断，返回的是最后那个满足的元素。（filter函数会返回集合中所有满足条件的元素）
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
