Optimized Brute Force with helper function (12ms)


  • 0
    S

    ...
    // Spread From Center
    void helper(const string& s, const int& idx, const int& offset, string& longest){
    int left = idx;
    int right = idx + offset;
    int currLength = 0;
    int ini=left;
    int end=right;
    while (left >= 0 && right<s.length() && s[left] == s[right]){
    ini=left;
    end=right;
    currLength = end-ini + 1;
    left--;
    right++;
    }

    if (tmpLength > longest.length())
    	longest = s.substr(ini,currLength);
    

    }

    string longestPalindrome(const string& s) {
    string longest = "";
    for (int i = 0; i < s.length(); i++){
    if(i+longest.length()/2>s.length())
    break;
    helper(s, i, 0,longest); // Odd case
    helper(s, i, 1, longest); // Even case
    }
    return longest;
    }
    ...


Log in to reply
 

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