[LeetCode] [Medium] Longest Palindromic Substring (dp)

1. Problem

Given s string and find longest palindromic substring

 

 

 

 

2. base: len

find palindromic based len: s.size() ~ 1  

 

bottom-up:

    iteration start => 1 -> s.size()

    You have to do unnecessary nested calculation. and must use dp algorithm.

 

top-down: i

    teration start => s.size() -> 1  

    If find palindromic, immediately return substring.

   

class Solution {
public:
    bool isPalindromic(string::iterator first, string::iterator last) {
        while(first != last && (first != --last)) {
            if(*(first++) != *last) return false;
        }
        return true;
    }
    string longestPalindrome(string s) {
        for(int len = s.size(); len >= 1; len--) {
            for(int i = 0; i + len <= s.size(); i++)
                if(isPalindromic(s.begin() + i, s.begin() + i + len))
                    return s.substr(i, len);
        }
        return s.substr(0, 1);
    }
};

 

 

 

 

3. base: center

Palindromic : left - center - right

 

and left == right

 

find all palindromic and return max len substring

 

Accepted 4ms c++ solution. - LeetCode Discuss

class Solution {
public:
    std::string longestPalindrome(std::string s) {
        if (s.size() < 2)
            return s;
        int len = s.size(), max_left = 0, max_len = 1, left, right;
        for (int start = 0; start < len && len - start > max_len / 2;) {
            left = right = start;
            while (right < len - 1 && s[right + 1] == s[right])
                ++right;
            start = right + 1;
            while (right < len - 1 && left > 0 && s[right + 1] == s[left - 1]) {
                ++right;
                --left;
            }
            if (max_len < right - left + 1) {
                max_left = left;
                max_len = right - left + 1;
            }
        }
        return s.substr(max_left, max_len);
    }
};

 

 

 

 

4.  Manacher's Algorithm

it is O(n) algorithm.

 

and based on center.

 

left - center - right

 

algospot.com :: Manacher's algorithm

 

this is only use 'odd palindromic'.

and if you want 'even', revise string to => s[0] + '#' + s[1] + '#' ....  

 

2*p -1 == i'

p == maximum r.. -> use: i is conclude r? => erase nested calc

r = p + d[p] 

 

5: if (i <= r) d[i] = min(d[2*p-i], r-i);

====> if conclude 

========> if have i' palindromic and conclude in r => can use it

========> but if it is bigger than r => cant' use it and  use r-i

==> if have not i'palindromic  => d[i] = 1

=>This tells you why you should use 'min' function

 

 

vector<int> manachers(string str){
  int N = str.size(), r = 0, p = 0;
  vector<int> d(N, 0);
  for (int i = 0; i < N; i++){
    if (i <= r) d[i] = min(d[2*p-i], r-i);
    while (i - d[i] - 1 >= 0 && i + d[i] + 1 < N 
      && str[i - d[i] - 1] == str[i + d[i] +1 ]) d[i]++;
    if (r < i + d[i]) {
      r = i + d[i];
      p = i;
    }
  }
  return d;
}

 

 

 

 

 

Longest Palindromic Substring - LeetCode