Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

一刷
题解：abbreviation, backtracking

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        bt(res, word, 0, "", 0);
        return res;
    }
    
    private void bt(List<String> res, String word, int pos, String cur, int count){
        if(pos == word.length()){
            if(count>0) cur+=count;
            res.add(cur);
        }
        else{
            bt(res, word, pos+1, cur, count+1);//abrevation the pos
            if(count>0){
                bt(res, word, pos+1, cur+count+word.charAt(pos), 0);
            }else{
                bt(res, word, pos+1, "" + word.charAt(pos), 0);
            }
        }
    }
}

二刷
类似于DFS, 分清abbreviation和not abbreviation的情况

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        //if(word == null || word.length()==0) return res;
        bt(word, 0, res, 0, "");
        return res;
    }
    
    private void bt(String word, int pos, List<String> res, int count, String cur){
        //abbreviation or not
        if(pos == word.length()){
            if(count>0) res.add(cur + count);
            else res.add(cur);
            return;
        }
        //abbreviation
        bt(word, pos+1, res, count+1, cur);
        
        //not abbreviation
        if(count != 0) bt(word, pos+1, res, 0, cur+count+word.charAt(pos));
        else bt(word, pos+1, res, 0, cur+word.charAt(pos));
    }
}