Palindrome

Palindrom

prefix == suffix and at most one in the middle


1. 9. Palindrome Number 

compare half of the digits in x, so don't need to deal with overflow.

public boolean isPalindrome(int x) {
    if (x<0 || (x!=0 && x%10==0)) return false;
    int rev = 0;
    while (x>rev){
     rev = rev*10 + x%10;
     x = x/10;
    }
    return (x==rev || x==rev/10);
}

5. Longest Palindromic Substring
https://leetcode.com/articles/longest-palindromic-substring/

Approach #1 (Brute Force)

The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome.

Complexity Analysis

• Time complexity : $O(n^3)$. Assume that $n$ is the length of the input string, there are a total of $\binom{n}{2} = \frac{n(n-1)}{2}$ such substrings (excluding the trivial solution where a character itself is a palindrome). Since verifying each substring takes $O(n)$ time, the run time complexity is $O(n^3)$.
• Space complexity : $O(1)$.

Approach #3 (Dynamic Programming) 

To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case $\text{''ababa''}$. If we already knew that $\text{''bab''}$ is a palindrome, it is obvious that $\text{''ababa''}$ must be a palindrome since the two left and right end letters are the same.

We define $P(i,j)$ as following:

$$P(i,j)=\{\begin{array}{cc}\text{true,}& \text{if the substring}{S}_i\dots S_j\text{is a palindrome}\\ \text{false,}& \text{otherwise.}\end{array}$$

Therefore,

$P(i, j) = ( P(i+1, j-1) \text{ and } S_i == S_j )$

The base cases are:

$P(i, i) = true$

$P(i, i+1) = ( S_i == S_{i+1} )$

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on...

Complexity Analysis

• Time complexity : $O(n^2)$. This gives us a runtime complexity of $O(n^2)$.
• Space complexity : $O(n^2)$. It uses $O(n^2)$ space to store the table.

   public String longestPalindrome(String s) {  
     int n = s.length();  
     int L[][] = new int[n][n];   
     char[] w = s.toCharArray();//faster compare  
     if(n == 0) return "";  
     for (int i = 0; i < n; i++)  
       L[i][i] = 1;  
     String ans = s.charAt(0)+"";  
     int max = 1;  
     for (int cl=2; cl<=n; cl++){  
       for (int i=0; i+cl-1<n; i++){  
         int j = i+cl-1;  
         if (cl == 2){  
           if(w[i] == w[j])  
            L[i][j] = 2;  
         }else{  
          if (w[i] == w[j] && L[i+1][j-1]!=0)  
           L[i][j] = L[i+1][j-1]+2;   
         }  
         if(cl > max&&L[i][j]!=0){  
           max =cl;  
           ans = s.substring(i,j+1);  
         }  
       }  
     }  
     return ans;  
   }  

Approach #3 (Expand Around Center) 

In fact, we could solve it in $O(n^2)$ time using only constant space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only $2n - 1$ such centers.

You might be asking why there are $2n - 1$ but not $n$ centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as $\text{''abba''}$) and its center are between the two $\text{'b'}$s.

public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int[] tmp1 = expandAroundCenter(s, i, i);
        int[] tmp2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(tmp1[2], tmp2[2]);
        if (len > end - start + 1) {
            if(len == tmp1[2]){
                start = tmp1[0];end=tmp1[1];
            }else{
                start = tmp2[0];end=tmp2[1];
            }
        }
    }
    return s.substring(start, end + 1);
}

private int[] expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    int[] ans = new int[3];
    ans[0] =L+1 ;ans[1] =R-1 ;ans[2] =R-L-1 ;
    return ans;
}

234. Palindrome Linked List

  public boolean isPalindrome(ListNode head) {  
     if(head == null) return true;  
     ListNode slow = head, fast = head;  
     while(fast.next!=null && fast.next.next != null){  
       slow = slow.next;  
       fast = fast.next.next;  
     }      
     slow = reverse(slow.next);  
     while(slow!=null){  
       if(slow.val != head.val) return false;  
       slow = slow.next;  
       head = head.next;  
     }  
     return true;  
   }  
   public ListNode reverse(ListNode head){  
     ListNode pre = null;  
     while(head!= null){  
       ListNode next = head.next;  
       head.next = pre;  
       pre = head;  
       head = next;  
     }  
     return pre;  
   }  

336. Palindrome Pairs

say we have string s, t. If they form a Palindrome s+t. Then one of it is suffix. We could build a suffix trie and loop through the word list as prefix. Find suffix in the trie.

When one of the word is exhausted, we need to know whether the other one is exhausted or it could form a Palindrome using the rest.

Because we need the index of the word. We store index of the word in Trie. And we also store the index list in node(if the rest of word could form Palindrome)

 public class Solution {  
   class TrieNode{  
     public TrieNode[] next;  
     public List<Integer> list;  
     public int index=-1;  
     public TrieNode(){  
       next = new TrieNode[26];  
       list = new ArrayList<>();  
     }  
   }  
   public List<List<Integer>> palindromePairs(String[] words) {  
     List<List<Integer>> ans = new ArrayList<>();  
     TrieNode root = new TrieNode();  
     constructSufixTrie(root,words);  
     for(int i = 0; i < words.length; i++){  
       String word = words[i];  
       TrieNode cur = root;  
       int j = 0;  
       for(; j < word.length(); j++){  
         char c = word.charAt(j);  
         if(cur==null)  
           break;  
         if(cur.index != -1){  //one exhausted
           if(cur.index != i && isPalindrome(word,j,word.length()-1))  
             ans.add(Arrays.asList(i,cur.index));  
         }  
         cur = cur.next[c-'a'];  
       }  
       if(j == word.length()&&cur!=null)  //the other exhausted
         for (int index : cur.list) {  
           if (i == index) continue;  
           ans.add(Arrays.asList(i, index));  
         }  
     }  
     return ans;  
   }  
   public void constructSufixTrie(TrieNode root,String[]words){  
     for(int i = 0; i < words.length; i++){  
       String word = words[i];  
       TrieNode cur = root;  
       for(int j = word.length()-1; j>=0;j--){  
         char c = word.charAt(j);  
         if(cur.next[c-'a']==null){  
           cur.next[c-'a'] = new TrieNode();  
         }  
         if (isPalindrome(word, 0, j) ){  
            cur.list.add(i);//!important  
         }  
         cur = cur.next[c-'a'];  
       }  
       cur.list.add(i);//!important  
       cur.index = i;  
     }  
   }  
   private boolean isPalindrome(String word, int i, int j) {  
        while (i < j) {  
             if (word.charAt(i++) != word.charAt(j--)) return false;  
        }  
        return true;  
   }  
 }  

214. Shortest Palindrome

The goal is to find longest Palindrome start from 0 index.

1.

The idea is to use two anchors j and i to compare the String from beginning and end.
If j can reach the end, the String itself is Palindrome.

Otherwise, that means ending at jth position could not form a palindrome start from 0 index. 

    int j = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == s.charAt(j)) { j += 1; }
    }
    if (j == s.length()) { return s; }
    String suffix = s.substring(j);
    return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;

2. LPS (longest proper prefix which is also suffix. )
because we want a longest palindrome with string prefix. Thus, we need to find suffix.

we could use s+'#'+reverse(s) to form suffix that of prefix.  Thus, we just need to find longest proper prefix which is also suffix. O(n)

  public String shortestPalindrome(String s) {  
     int n = s.length();  
     if(n == 0) return "";  
     String str = s+'#'+reverse(s);  
     int[] lps = new int [2*n+1];  
     int i = 1, len = 0;  
     while(i < 2*n+1){  
       if(str.charAt(i) == str.charAt(len)){  
         lps[i] = len+1;  
         len++;  
         i++;  
       }else{  
         if(len == 0)   
           i++;  
         else  
           len = lps[len-1];  
       }  
     }  
     return reverse(s.substring(lps[2*n]))+s;  
   }  

131. Palindrome Partitioning

For example, given s = "aab",
Return

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

   List<List<String>> resultLst;  
   public List<List<String>> partition(String s) {  
     resultLst = new ArrayList<List<String>>();  
     backTrack(s,0,new ArrayList<String>());  
     return resultLst;  
   }  
   public void backTrack(String s, int start,ArrayList<String> currLst){  
     if(currLst.size()>0   
       && start==s.length()){  
         List<String> r = (ArrayList<String>) currLst.clone();  
         resultLst.add(r);  
     }  
     for(int i = start; i<s.length(); i++){  
       if(isPalindrome(s,start,i)){  
         currLst.add(s.substring(start,i+1));  
         backTrack(s,i+1,currLst);  
         currLst.remove(currLst.size()-1);  
       }  
     }  
   }  
   public boolean isPalindrome(String s,int i, int j){  
     for(; i < j; i++,j--){  
       if(s.charAt(i)!=s.charAt(j)) return false;  
     }  
     return true;  
   }  
 }  

132. Palindrome Partitioning II

  public int minCut(String s) {  
     int n = s.length();  
     if(n == 0) return 0;  
     boolean[][] isPalindrome = new boolean[n][n];  
     int dp[] = new int[n+1];  
     for(int i = 2; i < n+1; i++) dp[i] = Integer.MAX_VALUE;  
     for(int i = 0; i < n; i++){  
       for(int j = 0; j <= i;j++){  
         if(s.charAt(i) == s.charAt(j)){  
           if(j+2>i)  
             isPalindrome[j][i] = true;  
           else  
              isPalindrome[j][i] = isPalindrome[j+1][i-1]||isPalindrome[j][i];  
         }    
       }  
     }  
     for(int i = 1; i < n; i++){  
        for(int j = 0; j <= i;j++){  
          if(isPalindrome[j][i]){  
           dp[i+1] = Math.min(dp[i+1], dp[j]+1);  
           if(j==0)  
             dp[i+1] = 0;  
          }  
        }  
     }  
     return dp[n];  
   }  

409. Longest Palindrome

public int longestPalindrome(String s) {  
     Map<Character, Integer> map = new HashMap<>();  
     int n = 0;  
     for(int i = 0; i < s.length(); i++){  
       char c = s.charAt(i);  
       map.putIfAbsent(c,0);  
       map.put(c,map.get(c)+1);  
       if((map.get(c)&1) == 0){  
         System.out.println(map.get(c));  
         n+=2;  
       }  
     }  
     if(n < s.length())  
       return n+1;  
     return n;  
   }  

267. Palindrome Permutation II

   List<String> ans = new ArrayList<>();  
   public List<String> generatePalindromes(String s) {  
     if(s.length()==0) return ans;  
     Map<Character,Integer> countMap = new HashMap<>();  
     for(int i = 0; i < s.length(); i++){  
       char c = s.charAt(i);  
       if(!countMap.containsKey(c))  
         countMap.put(c,1);  
       else   
         countMap.put(c,countMap.get(c)+1);  
     }  
     //check valid or not  
     char single = '\0';  
     for(Character key: countMap.keySet()){  
       if(countMap.get(key)%2==1){  
         if(single!='\0')  
           return ans;  
         single = key;  
       }  
     }  
     char[] ch = new char[s.length()];  
     if(single != '\0'){  
       ch[s.length()/2] = single;  
       countMap.put(single,countMap.get(single)-1);  
     }  
     dfs(ch,s.length()-1,0,(int)s.length()/2,countMap);  
     return ans;  
   }  
   public void dfs(char[] ch,int offset, int lo,int hi, Map<Character, Integer> countMap){  
     if(lo >= hi){  
       ans.add(new String(ch));  
     }  
     for(Character c: countMap.keySet()){  
       if(countMap.get(c)>1){  
         ch[lo] = c;  
         ch[offset-lo] = c;  
         countMap.put(c,countMap.get(c)-2);  
         dfs(ch,offset,lo+1,hi,countMap);  
         countMap.put(c,countMap.get(c)+2);  
       }  
     }  
   }