leetcode-5 Longest Palindromic Substring

題意: 求出最長回文子字串


解題思路:這題有許多解法,比如說動態規劃,不過在這裡筆者採用較為直觀的方法,也就是選定中心點,向兩端擴展,因為從字串內的每個字符考慮的話,其複雜度為$O(n^2)$,和動態規劃一樣,在這裡有個小技巧,可插入無關的元素,來簡化題目,這樣就不需考慮奇偶長度的回文串了,通通視為奇數長度處理


p.s 這題有O(n)算法,稱為Manacher's Algorithm,有需要可自行google


C++ code 如下:

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        string ns="";
        int maxl=0;
        
        int left;
        int right;
        for(int i=0;i<len;i++)
        {
            ns=ns+s[i];
            ns=ns+'*';
        }
        int len1=2*len;
        for(int i=0;i<len1;i++)
        {
            int rep=0;
            int j;
            if(ns[i]!='*')
                rep=1;
            for(j=1;(i-j>=0)&&(i+j<len1-1);j++)
            {
                if(ns[i-j]==ns[i+j])
                {
                    if(ns[i-j]!='*')
                        rep+=2;
                }
                else
                    break;
            }
            if(rep>maxl)
            {
                if(ns[i]=='*')
                {
                    left=i/2-rep/2+1;
                    right=i/2+rep/2;
                }
                else
                {
                    left=i/2-(rep-1)/2;
                    right=i/2+(rep-1)/2;
                }
                maxl=rep;
            }
        }
        string ans="";
        for(int i=left;i<=right;i++)
            ans=ans+s[i];
    
        return ans;   
    }
};