Generalized Abbreviation(Medium)

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"]

这道题第一步一定要理解题意，首先要考虑的是会有多少种结果。仔细观察会发现，最终会有Cn0 + Cn1 + Cn2 + ... + Cnn = 2^n种结果。 然后就很显然应该用DFS, 每次recursion存下当前结果，然后继续DFS。要注意下一步DFS的起始位置要与当前结束位置隔一个，否则就会出现有连续数字的结果，不希望出现连续数字的原因是因为连续数字可以合并成一个数字，已经算进去了，比如ab111就是ab3, 我们要的结果是ab3。

public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();

        dfs(res, "", 0, word);
        return res;
    }

    public void dfs(List<String> res, String curr, int start, String word) {
        //表示数字替换已经越界，recursion终止
        if (start > word.length())
            return;

        //用之前结束位置存入当前符合条件的结果
        res.add(curr + word.substring(start));

        //定义新的起始位置
        int i = 0;

        //除了最开始，起始位置都要与之前结尾位置隔一个
        if (start > 0) {
            i = start + 1;
        }

        for (; i < word.length(); i++) {
            String prefix = curr + word.substring(start, i);
            //以ith字符开头，依次替换j个字母成数字,数字之前的字符串要append上
            for (int j = 1; j <= word.length(); j++) {
                dfs(res, prefix + j, i + j, word);
            }
        }
}