Two-pointers (Palindrome)

[sync-by-unito[bot]]

FB Questions: //680. Valid Palindrome II

Classic: //5. Longest Palindromic Substring [Med] //214. Shortest Palindrome [Hard]

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//5. Longest Palindromic Substring

std::string longestPalindrome(std::string s) { if (s.size() < 2) return s; size_t i = 0, left = 0, right = 0; //runner index, left index, right index std::string maxStr = "";

while (i < s.size()) {
    //step1.find palindrome seeds:
    left = i;
    right = i;
    while (right < s.size() - 1 && s[right] == s[right + 1])
        right++;
    i = right + 1;

    //step2.extend the palindrome and find its length
    while (left > 0 && right + 1 < s.size() && s[left - 1] == s[right + 1]) {
        left--;
        right++;
    }

    //step3.get the longest palindrome
    maxStr = (maxStr.size() < right - left + 1) ? s.substr(left, right - left + 1) : maxStr;
}
return maxStr;

}

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//214. Shortest Palindrome

std::string shortestPalindrome(std::string s) {
    if (s.size() < 2) return s;
    int i = 0, left = 0, right = 0, max_ptr = 0;

    while (i <= s.size()/2) {
        //Step1. find possible palidrome seeds first, [l_ptr<->r_ptr] is possible seeds.
        left = i;
        right = i;
        while (s[left] == s[right + 1])
            right++;
        i = right+1;

        //Step2. extend the seed for a complete palindrome.
        while(left -1 >= 0 && right +1 < s.size() && s[left -1]==s[right +1])
        {
            left--;
            right++;
        }

        //Step3. get the shortest (l_ptr==0, r_ptr is the closest to far right)
        if (left == 0 && max_ptr < right)
            max_ptr = right;
    }

    //Step4. Fill chars started from anchor index to the string end, in front of the string to make it palindrome
    std::string tmp = s.substr(max_ptr + 1, s.size() - max_ptr);
    std::reverse(tmp.begin(), tmp.end());
    return tmp.append(s);
}

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//680. Valid Palindrome II

class Solution{ public: bool validPalindrome(std::string &s, size_t l, size_t r){ while(l < r){ if(s[l++] != s[r--]) return false; } return true; } bool validPalindrome(std::string &s){ size_t l = 0, r = s.size()-1; while(l < r){ if(s[l++] != s[r--]){ //Only one character to remove, check b1, b2 two ways bool b1 = validPalindrome(s, l, r+1); bool b2 = validPalindrome(s, l-1, r); return b1 || b2; } } return true; } };or Recursive:

class Solution{ public: //Recursive, this way can remove 'd' amount of characters bool validPalindrome(std::string &s, size_t l, size_t r, int d){ if(l >= r) return true; if(s[l] == s[r]) return validPalindrome(s, l+1, r-1, d); else{ return d > 0 && (validPalindrome(s, l+1, r, d-1) || validPalindrome(s, l, r-1, d-1)); } } bool validPalindrome(std::string &s){ return validPalindrome(s, 0, s.size()-1, 1); } };