leetcode320

经典的DFS加回溯，列举出全部的情况

public class test {
    private List<String> res;
    public List<String> generateAbbreviations(String word){
        res = new ArrayList<>();
        char[] chars = word.toCharArray();
        backtrack(chars, 0);
        res.add(word);
        return res;
    }

    private void backtrack(char[] chars, int start){
        if(start >= chars.length){
            return;
        }
        for(int i=start; i<chars.length; i++){
            char ch = chars[i];
            chars[i] = '@';
            res.add(toStr(chars));
            backtrack(chars, i+1);
            chars[i] = ch;
        }
    }

    private String toStr(char[] chars){
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<chars.length;){
            int j = i;
            int count = 0;
            if(chars[j] == '@'){
                while(j<chars.length && chars[j]=='@'){
                    j++;
                }
                sb.append(j-i);
                i = j;
            }else{
                sb.append(chars[j]);
                i++;
            }
        }
        return sb.toString();
    }
}