LeetCode

class Solution {
    private List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        //StringBuilder tempAddress = new StringBuilder();
        if(s.length() <=0){
            return result;
        }
        char[] temp = new char[s.length()+3];
        dfs(0, temp, s, 0);
        return result;
    }
    private void dfs(int dotCnt,char[] temp,String s,int sIdx){
        if(dotCnt == 4){
            if(sIdx == s.length()){
                result.add(new String(temp));
            }
            return;
        }

        for(int i = sIdx;i < sIdx+3 && i < s.length();i++){
            if(s.charAt(sIdx) == '0' && sIdx!=i){
                break;
            }

            String sub = s.substring(sIdx,i+1);
            if(Integer.parseInt(sub) > 255){
                break;
            }
            else{
                temp[i+dotCnt] = s.charAt(i);
                if(dotCnt!=3)
                    temp[i+dotCnt+1] = '.';
                dfs(dotCnt+1,temp,s,i+1);

            }

        }

        return;//可有可无
    }
}

class Solution {
    private String[] letterMap = new String[]{
        " ",    //0
        "",     //1
        "abc",     //2
        "def",     //3
        "ghi",     //4
        "jkl",     //5
        "mno",     //6
        "pqrs",     //7
        "tuv",     //8
        "wxyz",     //9
    };
    private List<String> list = new ArrayList<String>();
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")){
            return list;
        }
        char[] dp = new char[digits.length()];
        findCombination(digits,0,dp);
        return list;
    }

    private void findCombination(String digits,int index,char[] save){
        if(index == digits.length()){
            list.add(new String(save));
            return;
        }
        char c = digits.charAt(index);
        if(c < '0' || c > '9' || c == '1'){
            return;
        }

        String letters = letterMap[c - '0'];
        for(int i = 0;i < letters.length();i++){
            save[index] = letters.charAt(i);
            findCombination(digits,index+1,save);
        }

        //return;
    }
}

class Solution {
    private List<List<String>> result = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if(s.length() <= 0){
            return result;
        }
        ArrayList<String> temp = new ArrayList<>();
        dfs(s,0,temp);
        return result;
    }

    public void dfs(String s, int index, ArrayList<String> arr){
        if(index == s.length()){
            if(arr.size() > 0)
                result.add(new ArrayList<>(arr));

            return;
        }

        for(int i = index;i < s.length();i++){
            String sub = s.substring(index,i+1);

            if(isTrue(sub)){
                arr.add(sub);
                dfs(s,i+1,arr);
                arr.remove(arr.size()-1);
            }
        }
    }

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

dp[0][0] = true;
for(int j = 1; j < n; j++){
    for(int i = j; i>= 0; i--){
        if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i+1][j-1]))
            dp[i][j] = true;
    }
}

public class Solution {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null){
            return result;
        }
        ArrayList<Integer> temp = new ArrayList<>();
        dfs(root,target,temp);
        return result;
    }

    public void dfs(TreeNode root,int target,ArrayList<Integer> list){
        if(root.left == null && root.right == null){
            list.add(root.val);
            if(target == root.val && list.size()>0){
                result.add(new ArrayList<Integer>(list));
            }
            list.remove(list.size()-1);
            return;
        }

        list.add(root.val);
        if(root.left!=null)
        dfs(root.left,target-root.val,list);
        if(root.right!=null)
        dfs(root.right,target-root.val,list);
        list.remove(list.size()-1);

    }
}