LeetCode 5. Longest Palindromic Substring ( C )-Medium

題目為給定一個字串，請撰寫一支程式，回傳此字串中最長的迴文。

題目與範例如下

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: s = "cbbd"
Output: "bb"
Example 3:

Input: s = "a"
Output: "a"
Example 4:

Input: s = "ac"
Output: "a"
 
Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

我的解題策略為，遍歷字串的每個字元，以每個字元為起始點從前後比對字元是否相同。為了避免起始字元與旁邊的字元相等，先使用一個 while 迴圈，把與起始字元相同的字元都算進去，再開始左右比較。最後用動態記憶體配置創立一個要回傳的字元陣列，並把最長的迴文複製過去，回傳此字元陣列。

下面是我的程式碼

char * longestPalindrome(char * s){
    int start_index = -1,max = 0,temp = -1,tempL = 0,tempR = 0;
    for(int i = 0;i<strlen(s);i++){
        tempL = i;
        tempR = i;
        
        while(tempR+1<strlen(s)){
            if(s[tempR+1] == s[tempR])
                tempR++;
            else
                break;
        }
        
        while(tempL-1>=0 && tempR+1<strlen(s)){
            if(s[tempL-1] == s[tempR+1]){
                tempL--;
                tempR++;
            }
            else{
                break;
            }
        }
        
        if((tempR-tempL+1)>max){
            max = tempR-tempL+1;
            start_index = tempL;
        }
    }
    
    char *r = (char*)malloc((max+1)*sizeof(char));
    strncpy(r, &s[start_index], max);
    r[max] = '\0';
    return r;
}

下面是時間與空間之消耗

Runtime: 12 ms, faster than 83.30% of C online submissions for Longest Palindromic Substring.

Memory Usage: 6.2 MB, less than 59.25% of C online submissions for Longest Palindromic Substring.

下一題連結 : LeetCode 6. ZigZag Conversion ( C )-Medium

方便的話請幫我點選網頁四周的廣告，一點點鼓勵是我繼續寫的動力