Palindrome Partitioning

palindrome Partitioning lc 131

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 class Solution {
     public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (s == null || s.length() == 0) return result;
        List<String> list = new ArrayList<String>();
        helper(result, list, s, 0);
        return result;
    }

    public void helper( List<List<String>> result,List<String> list, String s, int position ){
        if(position == s.length()){
            //if(list.size() != 0){
                result.add(new ArrayList<String>(list));
            //}
            return;
        }
        for(int i = position; i < s.length(); i++){
            String value = s.substring(position, i + 1);
            if(isValid(value)){
                list.add(value);
                helper(result, list, s, i + 1);
                list.remove(list.size() - 1);
            }
        }

    } 
    private boolean isValid(String s){
        if( s == null || s.length() <= 1) return true;
        for(int i = 0; i <= s.length()/2;i++){
            if( s.charAt(i) != s.charAt(s.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }
}

palindrome Partitioning II

最少cut

// version 1
// f[i] 表示前i个字母，最少可以被分割为多少个回文串,是分割成多少个，不是cut几次，分割成3个只要cut2次
// 最后return f[n] - 1

public class Solution {
    public int minCut(String s) {
        if(s == null || s.length() == 0) return 0;
        boolean[][] result = getIsPalindrome(s) ;
        int[] f = new int[s.length() + 1];
        for ( int i = 0; i <= s.length(); i++){
            f[i] = i;
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (result[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }        
        return f[s.length()] - 1;
    }

    private boolean[][] getIsPalindrome(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];

        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                isPalindrome[i][j] =  (s.charAt(i) == s.charAt(j) && ( j - i <= 2 || isPalindrome[i + 1][j -1]));
            }
        }

        return isPalindrome;
    }




    /*private boolean[][] getIsPalindrome(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }

        for (int length = 2; length < s.length(); length++) {
            for (int start = 0; start + length < s.length(); start++) {
                isPalindrome[start][start + length]
                    = isPalindrome[start + 1][start + length - 1] && s.charAt(start) == s.charAt(start + length);
            }
        }

        return isPalindrome;
    }*/
}

判断palindrome boolean的好方法

 private boolean[][] getIsPalindrome(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];

        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                isPalindrome[i][j] =  (s.charAt(i) == s.charAt(j) && ( j - i <= 2 || isPalindrome[i + 1][j -1]));
            }
        }

        return isPalindrome;
    }