Leetcode -- Day 54 & Day 55 & Day 56

palindrome

Question 1

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.

What's very smart here is start from a character, and get its i-1 and i+1 for compare.

    public String longestPalindrome(String s) {
        if (s == null || s.length() <=1)
            return s;
        
        int start = 0;
        int longest = 0;
        for (int i = 0; i < s.length();){
            int p1 = i;
            int p2 = i;
            while(p2<s.length()-1 && s.charAt(p2) == s.charAt(p2+1)){
                p2 ++;
            }
            i = p2 + 1;
            while(p1>0 && p2<s.length()-1 && s.charAt(p1-1) == s.charAt(p2+1)){
               p1--;
               p2++;
            }
            int len = p2 - p1 + 1;
            if (len > longest){
                start = p1;
                longest = len;
            }
        }
        return s.substring(start, start + longest);
    }

Question 2

Palindrome Number

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

    public boolean isPalindrome(int x) {
        if (x < 0){
            return false;
        }
        int base = 1;
        while (x/base >= 10){
            base *= 10;
        }
        while (x != 0){
            int left = x / base;
            int right = x % 10;
            if (left != right){
                return false;
            }
            x = x % base;             // filter the most important digit
            x = x / 10;               // filter the least important digit
            base = base / 100;        // divide by 100, because already filter 2 digits
        }
        return true;
    }

Question 3 

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

    public boolean isPalindrome(String s) {
        s = s.trim();
        s = s.toLowerCase();
        int left = s.length() - 1;
        int right = 0;
        
        while (left >= right){
            char c1, c2;
            if (!Character.isLetterOrDigit(s.charAt(left))){
                left --;
            }
            else if (!Character.isLetterOrDigit(s.charAt(right))){
                right ++;
            }
            else{
                c1 = s.charAt(left);
                c2 = s.charAt(right);
                if (c1 != c2){
                    return false;
                }
                left --;
                right ++;
            }
        }
        return true;
    }

Question 4

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"]
  ]

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<List<String>>();
    dfs(new ArrayList<String>(), s, res);
    return res;        
}
//depth-first-search
public void dfs(List<String> path, String s, List<List<String>> res){
    if(s.length() == 0){
        res.add(path);
        return;
    }
    for(int i = 1; i <= s.length(); i++){//i start from 1, to use the substring method
        if(isPalin(s.substring(0,i))){
            List<String> extendedPath = new ArrayList<String>(path);
            extendedPath.add(s.substring(0,i));
            dfs(extendedPath, s.substring(i),res);
        }
    }
}
public boolean isPalin(String s){
    for(int i = 0; i < s.length()/2; i++){
        if(s.charAt(i) != s.charAt(s.length()-1-i)) return false;
    }
    return true;
}

Question 5

Palindrome Partitioning II

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

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

    public int minCut(String s) {  
        int min = 0;  
        int len = s.length();  
        boolean[][] matrix = new boolean[len][len];  
        int cuts[] = new int[len+1];  
          
        if (s == null || s.length() == 0)  
            return min;  
         
        for (int i=0; i<len; ++i){  
            cuts[i] = len - i;  //cut nums from i to len [i,len]
        }  
          
        for (int i=len-1; i>=0; --i){  
            for (int j=i; j<len; ++j){  
                if ((s.charAt(i) == s.charAt(j) && (j-i<2))  
                        || (s.charAt(i) == s.charAt(j) && matrix[i+1][j-1]))  
                {  
                    matrix[i][j] = true;  
                    cuts[i] = Math.min(cuts[i], cuts[j+1]+1);  
                }  
            }  
        }  
        min = cuts[0]-1;  
        return min;  
    }