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

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();

        dfs(word, new StringBuilder(), ans, 0, 0);

        return ans;
    }

    private void dfs(String word, StringBuilder sb, List<String> ans, int i, int k){
        int len = sb.length();

        if (i == word.length()){
            if (k > 0) sb.append(k);
            ans.add(sb.toString());
        }else{
            // Abbreviations
            dfs(word, sb, ans, i + 1, k + 1);

            // non-Abbreviations
            if (k > 0) sb.append(k);
            sb.append(word.charAt(i));
            dfs(word, sb, ans, i + 1, 0);

        }

        sb.setLength(len);    
    }
}