LEET code--Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

反正就是找回文
太久沒寫  沒手感阿
字串處理根本忘光

暴力解 又太慢....
因為沒有處理重複字元的關係

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

char* longestPalindrome(char* s) { if(s==NULL){ return NULL; } int size = strlen(s); int i=0,max=0,start=0; for(i=0;i<size;i++){ int last = size-1; while( last>=i){ if(s[i] == s[last]){ int j=0; while(s[i+j]==s[last-j] &&last-j>=i+j)j++; if ( (last-i+1)%2==0 ){ if(i+j - (last-j) ==1){ if(last-i+1 > max){ max=last-i+1; start=i; } } }else{ if(i+j - (last-j) ==2){ if(last-i+1 > max){ max=last-i+1; start=i; } } } } last--; } } char *head=(char*)malloc(sizeof(char)*max); strncpy(head,s+start,max); return head; }

------------------------------------------------

最佳解:
用三種指標
最左邊，中間，最右邊
每次先讓最右邊去跑重複字串，最左邊跟中間再慢慢增加，這樣可以避免重複字串浪費時間

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

char* longestPalindrome(char* s) { if(s==NULL){ return NULL; } int size = strlen(s); if(size==1)return s; int i=0,max=0,start=0; int left=0,right=0; for(i=0;i<size;){ if(max/2 > size-i)break; left=i; right=i; while(s[right] == s[right+1] && right<size-1)right++; i=right+1; while(left>0 &&right<size-1 && s[left-1]==s[right+1]){left--;right++;} if(right-left+1 > max){ max=right-left+1; start=left; } } char *head=(char*)malloc(sizeof(char)*max); strncpy(head,s+start,max); head[max]='\0'; return head; }

------------------