Write a function to generate the generalized abbreviations of a word.

Note: The order of the output does not matter.

Example:

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

这道题其实总体来说是个DFS的题，但是也可以backtracking，具体细节没太想明白，看了看答案

遍历这个字符串，如果当前字符被用数字代替（不管是单个还是多个），则递归调用helper(res, curr, word, i + 1, k + 1)，这里k用于代替字符的数字。如果当前字符没有被代替，k如果为0，则不把k加入curr，如果k不为0，则加入curr，并把当前的字符也加入curr

由于是先加入k再加入字符，所以避免了两个数字相连的情况

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        if(word == null)
            return res;

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

    public void helper(List<String> res, String curr, String word, int i, int k) {
        if(i == word.length()) {
            if(k != 0)
                res.add(curr + k);
            else
                res.add(curr);

            return;
        }

        helper(res, curr, word, i + 1, k + 1);

        if(k == 0)
            helper(res, curr + word.charAt(i), word, i + 1, 0);
        else
            helper(res, curr + k + word.charAt(i), word, i + 1, 0);
    }
}