C++_Accepted_36ms_73.74%


  • 0
    #Code1:  63 ms, 58,86%#
    class Solution {
    public:
        string longestPalindrome(string s) {
        int n = s.size();
        int len = 0;
        int start = 0, end = 0;
        for(int i = 0; i < n; i++){
            int len1 = Center(s, i,i);
            int len2 = Center(s, i,i+1);
            len = max(len1,len2);
            if(end - start + 1 < len){
                start = i - (len - 1)/2;
                end = i + len/2;
            }
        }
        return s.substr(start,end - start + 1);
    }
    
    int Center(string s, int left, int right){
        while(left >= 0 && right < s.size()){
            if(s[left] == s[right]){
                left--;
                right++;
            }else{break;}
        }
        return right - left + 1 - 2;//because the last loop has made the right and left to increase and decrease 1
    }   };
    
    
    
    
    #Code2: 36ms, 73.74%, much more clean and clear#
    class Solution {
    public:
    string longestPalindrome(string s) {
        int n = s.size();
        int len = 0;
        int start = 0, end = 0;
        for(int k = 0; k < n; k++){
            int i = k, j = k;
            while(i >= 0 && j < n && s[i] == s[j]){
                i--;
                j++;
            }
            len = max(j - i - 1,len);
            
            i = k, j = k+1;
            while(i >= 0 && j < n && s[i] == s[j]){
                i--;
                j++;
            }
            len = max(j - i - 1,len);
            
            if(len > end - start + 1){
                start = k - (len - 1)/2;
                end = k + len/2;
            }
        }
        return s.substr(start,end - start + 1);
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.