#5. Longest Palindromic Substring

題目描述

給你一個字串s，回傳s中最長的回文子字串。

限制條件

1 <= s.length <= 1000
s只由數字和英文字母組成。

解題思路

回文的意思是由前往後念和由後往前念都是一樣的，從另一個角度來說我們從回文中間開始同時往前後兩個方向檢查字元，字元都會是一致的。

舉例來說：
s = "abccba"，從中間同時往前後兩個方向檢查字元，第一個遇到的會是c，前後都是一樣的，第二個字元則是b，第三個字元則是a，所以前後所指向兩個字元都會是一樣的。

知道這點後要找到最長的回文，只要在字串的每個位置上，做一次前後字元的檢查，就可以檢查到最長的回文。

要注意的是，回文不一定都是偶數，也有可能會出現奇數的回文，因此也要做一個奇數的對應處理。

Solution

public class Solution {
    public string LongestPalindrome(string s) {
        string ans ="";
        for(int i=0;i<s.Length;i++){
            string a = PalindromeCounter(s,i,i);
            string b = "";
            if(i>0) b = PalindromeCounter(s,i-1,i);            
            if(ans.Length<a.Length) ans = a;
            if(ans.Length<b.Length) ans = b;            
        }
        return ans;
    }

    public string PalindromeCounter(string s, int left, int right){
        int count = 0;        
        while(left>=0 && right<s.Length){
            if(s[left]!=s[right]){
                return s.Substring(left+1,count);           
            }
            if(left == right){
                count += 1;
            }else{
                count += 2;
            }
            left--;
            right++;
        }
        return s.Substring(left+1,count);
    }
}

複雜度分析：

時間複雜度：時間複雜度為O(n^2)。
空間複雜度：空間複雜度為O(1)。

學習重點

String