Palindrome in LeetCode

There are four problems in Leetcode about dealing with palindormes.

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution1: Recursion

When face the "return all", "get all ", "find all possible", "find the total number of", an idea is to use the recursion. Same as this problem!

To get the all the partitions of a string s:
1. find all the palindromes in substring s[0], and all the palindromes in substring s[1:end]
2. find all the palindromes in substring s[0:1], and all the palindromes in substring s[2:end]
...
find all the palindromes in substring s[1:end-1], and all the palindromes in substring s[end]

So the problem is quite clear, when we do recursion, two things should be considered:
1. stop condition:  when the search goes to the last position in the string
2. for loop or while loop:   for position=current start position to the end.

Code:

class Solution {

public:

  bool valid(string &str, int st, int ed){

        while (st<ed){

            if (str[ed]!=str[st]){

                return false;

            }else{

                st++;

                ed--;

            }

        }

        return true;

    }

     

  void find(string s, int st, vector<string> &r, vector<vector<string> > &res){

        if (st>=s.size()){

            res.push_back(r);

        }else{

        for (int i=st;i<s.size();i++){           

            if (valid(s,st,i)){

                r.push_back(s.substr(st,i-st+1));///!!!!

                find(s,i+1,r,res);       

                r.pop_back();///!!!!

            }

        } 

    }

  vector<vector<string>> partition(string s) {

        vector<vector<string> > res;

        vector<string> r;

        find(s,0,r,res);

        return res;   

    }

};

Solution 2: DP to reduce redundent computation.
P[i][j] means that the substring from i to j is palindrome.
Optimal function:
   p[i][j]==1 if p[i+1][ j-1]=1 and s[i] = s[j]

Initial state:
   P[i][i] =1; 奇
   p[i][i+1]=1 if(s[i]==s[i+1]); 偶


After populating the array, use backtrack to recursively get all possible solution. Backtrack is almost the same with solution one. 认真体会两种不同的在递归过程中传递数据的方式

Code:

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.


Solution: Similar method to solve this problem.

Use maxLen to identify the maximum length of palindrome and the start and end indices.
The problem can be solve in O(n)
At http://www.akalin.cx/longest-palindrome-linear-time

Of course, the most naive solution would be to exhaustively examine all (n2) substrings of the given n-length string, test each one if it's a palindrome, and keep track of the longest one seen so far. This has complexity O(n3), but we can easily do better by realizing that a palindrome is centered on either a letter (for odd-length palindromes) or a space between letters (for even-length palindromes). Therefore we can examine all 2n+1 possible centers and find the longest palindrome for that center, keeping track of the overall longest palindrome. This has complexity O(n2).

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.