Java backtrace solution


  • 0
    L
    List<List<String>> res = new ArrayList<List<String>>();
    public List<List<String>> partition(String s) {
        if(s == null || s.length() == 0) return res;
        dfs(s,0,new ArrayList<>());
        return res;
    }
    private void dfs(String s,int start,List<String> cur){
        if(start == s.length()){
            res.add(new ArrayList<String>(cur));
            return;
        }
        for(int i = start+1; i <= s.length(); i++){
            if(isPalindrome(s,start,i-1)){
                cur.add(s.substring(start,i));
                dfs(s,i,cur);
                cur.remove(cur.size()-1);
            }
        }
    }
    boolean isPalindrome(String s, int start,int end){
        while(start < end){
            if(s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.