Palindrome Partitioning 136

Question

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

Return all possible palindrome partitioning of s.

Example

Given s = "aab", return:

[ ["aa","b"],

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

Solution

Recursion

Recursion: 类似Subsets。递归含义位：以path开头，s从第pos到结尾的字符串是否为回文串。

Non-Recursion：用位运算的方法，但是总时间会超时。

代码如下：

Recursion:

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public ArrayList<ArrayList<String>> partition(String s) {
        // write your code here
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        if (s == null) {
            return result;
        }

        ArrayList<String> path = new ArrayList<String>();
        helper(s, path, 0, result);

        return result;
    }

    private void helper(String s, ArrayList<String> path, int pos, ArrayList<ArrayList<String>> result){
        if(pos == s.length()){
            result.add(new ArrayList<String>(path));
            return;
        }

        for(int i = pos + 1; i <= s.length(); i++){
            String sb = s.substring(pos, i);
            if(!isPalindrome(sb)){
                continue;
            }

            path.add(sb);
            helper(s, path, i, result);
            path.remove(path.size() - 1);
        }
    }

    private boolean isPalindrome(String s){
        int length = s.length();
        if(length == 1){
            return true;
        }

        for(int i = 0, j = length - 1; i <= j; i++, j--){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

Non-Recursion: 超时

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public ArrayList<ArrayList<String>> partition(String s) {
        // write your code here
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        if(s == null || s.length() == 0){
            return result;
        }

        int n = s.length() - 1;
        for(int i = 0; i < Math.pow(2, n); i++){
            int last = 0;
            ArrayList<String> list = new ArrayList<String>();
            int j = 0;
            for(; j < n; j++){
                if((i & (1 << j)) != 0){
                    String sb = s.substring(last, j + 1);
                    if(!isPalindrome(sb)){
                        break;
                    }
                    list.add(sb);
                    last = j + 1;
                }
            }
            if(j == n){
                if(isPalindrome(s.substring(last))){
                    list.add(s.substring(last));
                    result.add(list);
                }else{
                    continue;
                }
            }else{
                continue;
            }
        }

        return result;
    }

    private boolean isPalindromeList(ArrayList<String> list){
        for(String s : list){
            if(!isPalindrome(s)){
                return false;
            }
        }
        return true;
    }

    private boolean isPalindrome(String s){
        int length = s.length();
        if(length == 1){
            return true;
        }

        for(int i = 0, j = length - 1; i <= j; i++, j--){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}