LeetCode 5. Longest Palindromic Substring (*´▽`*)

　　本題難度為 medium，剛開始看到題目就傻住了，知道要用 Dynamic Programming 的解法，不然可能會超時，看一下台師大的演算法筆記，原來這種題目時間複雜度是O(N^4)，例如 Uva 12473，參考中英文的資料後，用習慣的 C 語言，總算是把這題解出來了，大半夜我就懶得修程式碼了，等起床再把程式整理一下比較容易理解，這題算是很常見的題目，非常有趣，順便練習一下在函數裡回傳字串，最後感謝其他博主的心得分享，幫了我很多，晚安~


char * longestPalindrome(char * s){
       int i,j,len;
       len = strlen(s);
       int maxlen;
       int omaxlen=0;
       int begin=0;
       int array[1000][1000];
       int llen;
       for(i=0;i<1000;i++){
           for(j=0;j<1000;j++){
               if(i==j) array[i][j]=1;
               else     array[i][j]=0;
           }
       }
       for(i=0;i<len-1;i++){
           if(s[i]==s[i+1]){
               array[i][i+1]=1;
               maxlen=2;
               if(maxlen>omaxlen){
                    omaxlen=maxlen;
                    begin=i;
               }
           }
       }
       for(llen=3;llen<=len;llen++){
           for(i=0;i<len-llen+1;i++){
               j=i+llen-1;
               if(i+1>j-1){
                    if(array[i][j-1]==1 && s[i]==s[j]){
                        array[i][j]=1;
                        maxlen=j-i+1;
                        if(maxlen>omaxlen){
                            omaxlen=maxlen;
                            begin=i;
                        }
                    }else array[i][j]=0;
               }else{
                    if(array[i+1][j-1]==1 && s[i]==s[j]){
                        array[i][j]=1;
                        maxlen=j-i+1;
                       // printf("%d %d %d\n",i,j,maxlen);
                        if(maxlen>omaxlen){
                            omaxlen=maxlen;
                            begin=i;
                        }
                    }else array[i][j]=0;
               }
              // printf("array[%d][%d]=%d\n",i,j,array[i][j]);
           }
       }
       static char ans[1001];
       memset(ans,0,1001);
      // printf("%d\n%d\n",begin,omaxlen);
       strncpy(ans,s+begin,omaxlen);
       if(omaxlen==0) strncpy(ans,s,1);
       if(len==1) return s;
       else return ans;
}


參考資料：
[1]　http://www.csie.ntnu.edu.tw/~u91029/Palindrome.html
[2]    https://medium.com/@ChYuan/leetcode-no-322-longest-palindromic-substring-%E5%BF%83%E5%BE%97-medium-3ff9eff34230
[3]    https://skylinelimit.blogspot.com/2018/02/c-2.html
[4]    https://openhome.cc/Gossip/CGossip/StringLengthCopyCat.html

[5]    https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

[6]    https://stackoverflow.com/questions/6205195/given-a-starting-and-ending-indices-how-can-i-copy-part-of-a-string-in-c