131. Palindrome Partitioning

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:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Thinking:

• Method1:
  • 通过递归实现。
  • 扫描每一位可能并通过回溯，当index的长度和字符串的长度一致时添加进入结果。

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if(s == null || s.length() == 0) return result;
        backtrace(s, result, new ArrayList<String>(), 0);
        return result;
    }
    public static void backtrace(String s, List<List<String>> result, List<String> list, int index){ //index: end position
        if(index == s.length()) result.add(new ArrayList<String>(list));
        else{
            for(int i = index + 1; i <= s.length(); i++){
                String sub = s.substring(index, i);
                if(isPalindrome(sub)){
                    list.add(sub);
                    backtrace(s, result, list, i);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
    private static boolean isPalindrome(String s){
        int len = s.length();
        if(len == 0 || len == 1) return true;
        int half = len / 2;
        int low = -1, high = len;
        while(++low < len && --high >= 0 && low <= high){
            char c1 = s.charAt(low);
            char c2 = s.charAt(high);
            if(c1 != c2) return false;
        }
        return true;
    }
}

二刷

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new LinkedList<>();
        if(s == null) return result;
        backtrace(s, result, new LinkedList<String>(), 0);
        return result;
    }
    private void backtrace(String s, List<List<String>> result, List<String> temp, int index){
        if(index == s.length()) result.add(new LinkedList<String>(temp));
        else{
            for(int i = index + 1; i <= s.length(); i++){
                String cur = s.substring(index, i);
                if(isPalindrome(cur)){
                    temp.add(cur);
                    backtrace(s, result, temp, i);
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }
    private boolean isPalindrome(String s){
        int len = s.length();
        if(len == 0) return true;
        int low = -1, high = len;
        char[] arr = s.toCharArray();
        while(low <= high){
            if(++low < len && --high >= 0)
                if(arr[low] != arr[high])
                    return false;
        }
        return true;
    }
}

Third time

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if(s.length() == 0){
            result.add(new ArrayList<>());
            return result;
        }
        dfs(result, s, new ArrayList<String>(), 0);
        return result;
    }
    private void dfs(List<List<String>> result, String s, List<String> temp, int start){
        if(start == s.length())  result.add(new ArrayList<String>(temp));
        else{
            for(int i = start + 1; i <= s.length(); i++){
                String sub = s.substring(start, i);
                if(isPalindrome(s.substring(start, i))){
                    temp.add(sub);
                    dfs(result, s, temp, i);
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }
    private boolean isPalindrome(String s){
        int len = s.length();
        if(len == 1) return true;
        char[] arr = s.toCharArray();
        int start = 0, end = len - 1;
        while(start < end){
            if(arr[start++] != arr[end--]) return false;
        }
        return true;
    }
}