Leetcode 5. Longest Palindromic Substring

Longest Palindromic Substring :

此題給一個字串s，找到最大的『回文子字串』，palindromic(回文)的意思就是字串顛倒也是一樣的。

按每個字符迭代整個字符串。對於每個字符，有兩個指針。

• 左指針：前一個字符相對於當前字符的索引。
• 右指針：當前字符下一個字符的索引。

條件

• 如果前一個字符和下一個字符相同。將左指針向左移動一個索引，並將右指針向右移動。
• 如果索引外的左指針或右指針或前一個字符和下一個字符不相等，則返回左右指針之間範圍內的字符串。如果返回的字符串比最長的字符串長，則用返回的字符串替換最長的字符串。

完成迭代後，返回最長的字符串作為答案

時間複雜度: O(n*n/2)

空間複雜度: O(1)

Python

雙指針

class Solution:
    def longestPalindrome(self, s: str) -> str:
            longest = ''
            def findLongest(s, l, r):
                while l>=0 and r<len(s) and s[l] == s[r]:
                    l-=1
                    r+=1
                return s[l+1:r]

            for i in range(len(s)):
                s1 = findLongest(s, i, i)
                if len(s1) > len(longest): longest = s1

                s2 = findLongest(s, i, i+1)
                if len(s2) > len(longest): longest = s2

            return longest

動態規劃

def longestPalindrome(self, s: str) -> str:
        longest = '' if not s else s[0]
        max_len = 1
        size = len(s)
        dp=[[False]*size for _ in range(size)]
        for start in range(size-1,-1,-1):
            dp[start][start]=True
            for end in range(start+1,size):
                if s[start]==s[end]:
                    if end - start == 1 or dp[start+1][end-1]:
                        dp[start][end] = True
                        if max_len < end - start + 1:
                            max_len = end - start + 1
                            longest = s[start: end+ 1]
        return longest

C++

getLen 如果左右有相等的數，則左邊向左跟右邊向右繼續比較，返回回文總長度

cur分為偶數個數跟奇數個數，所以要比哪個長度最長

class Solution {
public:
  string longestPalindrome(string s) {
    const int n = s.length();
    auto getLen = [&](int l, int r) {
      while (l >= 0 && r < n 
             && s[l] == s[r]) {
        --l;
        ++r;
      }
      return r - l - 1;    #返回回文總長度
    };
    int len = 0;
    int start = 0;
    for (int i = 0; i < n; ++i) {
      int cur = max(getLen(i, i),         #偶數個數跟奇數個數，取最大長度
                    getLen(i, i + 1));
      if (cur > len) {
        len = cur;
        start = i - (len - 1) / 2;    #開始位置，分為奇數跟偶數情況
      }
    }
    return s.substr(start, len);
  }
};