Given a strings, partitionssuch that every substring of the partition is a palindrome.

Return all possible palindrome partitioning ofs.

For example, givens="aab", Return

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

Solution: 类似subset

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        if(s == null){
            return result;
        }
        List<String> path = new ArrayList<String>();
        helper(s, result, path, 0);
        return result;
    }
    private void helper(String s, List<List<String>> result, List<String> path, int start){
        if(start == s.length()){
            result.add(new ArrayList<String>(path));
            return;
        }
        for(int i = start + 1; i <= s.length(); i++){
            String prefix = s.substring(start, i);
            if(!isPalindrome(prefix)){
                continue;
            }
            path.add(prefix);
            helper(s, result, path, i);
            path.remove(path.size() - 1);
        }
        return;
    }

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

results matching ""

    No results matching ""