算法设计与分析-Week2

发表于 | 更新于

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”

解题思路

题目要求所给字符串的最长回文子字符串。

解法一

暴力求解。任选子字符串的两端，并验证该字符串是否为回文字符串，由于端点的两两选择需要\(O(n^2)\)的复杂度，验证字符串需要\(O(n)\)的复杂度，所以整个算法需要\(O(n^3)\)的时间复杂度。

解法二

并不需要对每个字符串都进行回文字符串的验证，假如一个字符串是回文字符串，那么如果其两侧的字符相同，则新的字符串也是回文字符串，这样就不用对新的字符串进行从头到尾的验证，从而把时间复杂度从\(O(n)\)降为\(O(1)\)。由所给的两个样例可以看出，回文字符串根据字符串的长度可分为奇偶两种，因此只要选好中心位置，沿着中心位置向两边进行扩展，就能得到该中心位置的最长回文字符串，遍历所有中心位置，就能得到最长的回文字符串，总的时间复杂度为\(O(n^2)\)。

源代码

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
26
27
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length() == 0) return "";
        int start, length = 0;
        for(int i = 0; i < s.length(); i++) {
            int len1 = maxLength(i, i, s);
            int len2 = maxLength(i, i + 1, s);
            if(len1 > len2 && len1 > length) {
                start = i - len1 / 2;
                length = len1;
            }
            else if(len1 < len2 && len2 > length) {
                start = i - len2 / 2 + 1;
                length = len2;
            }
        }
        return s.substr(start, length);
    }
    int maxLength(int left, int right, string s) {
        while(left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
};
0%