首页 > 代码库 > [Leetcode] 5 - Longest Palindromic Substring

[Leetcode] 5 - Longest Palindromic Substring

题目链接:https://oj.leetcode.com/problems/longest-palindromic-substring/


这道题通常可以写出来的是2种做法。

1. 保持一个index从前往后扫,每次index的循环中,保持left和right的index向两边扫,但是有2种情况,aba和abba。left和right的扫描要扫2次

2. DP做法,2维矩阵

* 可以适当减枝,比如当前index完全不可能提供比已经得到的最长string再长的可能,则移动到下一个index


class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return "";
        
        int idx = 0;
        int maxLen = 0;
        string res;
        
        while (idx < s.size()) {
            // break if even the longest palindrome string we could get
            // is still shorter than the maximun one we have
            if (min(s.size() - idx, idx + 1) * 2 <= maxLen) break;
            
            int left;
            int right;
            
            // 1st case, ex: aba
            left = idx;
            right = idx;
            while (left >= 0 && right < s.size()) {
                if (s[left] == s[right]) {
                    if (maxLen < right - left + 1) {
                        maxLen = right - left + 1;
                        res = s.substr(left, right - left + 1);
                    }
                    --left;
                    ++right;
                } else {
                    break;
                }
            }
            
            // 2nd case, ex: abba
            left = idx;
            right = idx + 1;
            while (left >= 0 && right < s.size()) {
                if (s[left] == s[right]) {
                    if (maxLen < right - left + 1) {
                        maxLen = right - left + 1;
                        res = s.substr(left, right - left + 1);
                    }
                    --left;
                    ++right;
                } else {
                    break;
                }
            }
            
            ++idx;
        }
        
        return res;
    }
};


[Leetcode] 5 - Longest Palindromic Substring