5. Longest Palindromic Substring

1.問題

• 給予一個字串, 找出長度最長的回文字串, 可以假設最長的字串長度為1000

2.想法

• 提問: 字串是否可以是0

• function header, parameter, return value

• example input

• 說明想法

  • 移動罩窗, 以每個字元為中心, 有奇數罩窗與偶數罩窗兩個case, 如果left == right, 則繼續擴大罩窗, 不然就回傳sub string

  • 注意c++ 取substring的用法

• 測試

• 計算複雜度: O(n)?

3.程式碼

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.length();
        string res("");
        if (size == 0 || size == 1) {
            return s;
        }
        for (int i = 0; i< size - 1; i++) {
            //奇數
            string odd = getMaxPalindrome(s, i, i); 
            if (odd.length() > res.length()) {
                res = odd;
            }
            //偶數
            string even = getMaxPalindrome(s, i, i + 1);
            if (even.length() > res.length()) {
                res = even;
            }
        }
        return res;
    }
private:
    string getMaxPalindrome(string s, int left, int right) {
        while (left < s.size() && 
               right >= 0 &&
               s[left] == s[right]) {
            right++;
            left--;
        }
        //right減回去, left加回去
        //string取sub string的用法
        return s.substr(left+1, (right - 1) - (left + 1) + 1);
    }
};

4.Performance