算法
February 9, 2019

Longest Palindromic Substring

版权声明：本文为博主原创文章，转载请注明原文出处！

写作时间：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:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

题目要求我们找到给定字符串中的所有回文子串中最长子串。

思路分析

这个题目和之前的LeetCode-Palindromic Substrings题目的思路是一样的，Palindromic Substrings是找回文的个数。在这个过程中其实我们是找出了所有的回文子串，接下来我们统计一下每个回文的长度，选择出最长的那个就是本文的答案了（当然，在代码实现过程中统计最长子串不一定是找到了所有的子串之后再统计，可能是边寻找边统计）。所以，方法还是老方法，可以利用动态规划，也可以利用中心扩散法。

有不明白的地方可以参见我之前的博文《LeetCode-Palindromic Substrings》，这里我只给出了使用中心扩散法进行求解的代码实现。

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)
      }
    }
  }
}

这里需要注意的是：

  1. 需要对于空字符串的特殊处理（这里使用的是match匹配，当然也可以使用if...else条件语句）

  2. 我们使用yield每次生成回文子串的左右指针，然后再使用maxBy得到最长子串对应的左右指针。

  3. takeWhile函数对集合进行遍历过程中当条件不满足的时候会立即停止判断，返回的是最后那个满足的元素。（filter函数会返回集合中所有满足条件的元素）