Palindrome Partitioning II -interesting

 //there is a related problem: longest palindrome substring
Note that in the following solution, to accommodate the dp computation of palin, we define dp[i] to be the mincut for the substring from i to the end.
     int minCut(string str) {
        int leng = str.size();

        int dp[leng+1];
        bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i-1;
      for(int i = 0; i < leng; i++)
          for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(str[i] == str[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0];
    }

 //one dimension dp, by anniekim
   int minCut(string s) {
        int N = s.size();
        bool isP[N];
        int dp[N];
        dp[0] = 0;
        for (int i = 1; i < N; ++i)
        {
            isP[i] = true;
            dp[i] = dp[i-1] + 1;
            for (int j = 0; j < i; ++j)
            {
                isP[j] = (s[i] == s[j]) ? isP[j+1] : false; // isP[j] == true -> [j...i] is a palindrome
                                                            // isP[j+1] == true -> [j+1...i-1] is a palindrome
                if (isP[j])
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1); // dp[i] -> minCount for [0...i]
            }
        }
        return dp[N-1];
    }

Longest Palindromic Substring

first method: dp

    string longestPalindrome(string s) {
        if(s.length()==0)
            return "";
        bool palin[1000][1000] = {false};
        int maxLen = 0;
        int maxstart=0;
        for(int i=s.length()-1;i>=0;i--)
        {
            for(int j=i;j<s.length();j++)
            {
                if(s[i]==s[j] && (j-i<=2 || palin[i+1][j-1]))
                {
                    palin[i][j] = true;
                    if(maxLen<j-i+1)
                    {
                        maxLen=j-i+1;
                        maxstart=i;
                    }
                }
            }
        }
        return s.substr(maxstart,maxLen); 
    }

second method: Time O(n), Space O(n) (Manacher's Algorithm)
 the code is generally adopted from leetcode, but i have changed a little to satisfy my understanding.  There is another flavor written by anniekim.

string preProcess(const string &s) {
  int n = s.length();

  string ret;
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);

  ret += "#";
  return ret;
}

string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 0; i < n; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)
   
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
   
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])//actually need to check if the index is in the range.
      P[i]++;

    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }

  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 0; i < n; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;
 
  return s.substr((centerIndex  - maxLen)/2, maxLen);
}