320. Generalized Abbreviation

Problem:

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

Analysis:
There are 2^n (n is the length of word) possible abbreviations. Use DFS to get all abbreviations.

Solution:
If we skip the current char, we can not append the count, because we dont know if the next char would be skipped or not. We can make sure the count is set is when current char remains or we reach the end.

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        dfs(res, new StringBuilder(), word, 0);
        return res;
    }

    private void dfs(List<String> res, StringBuilder sb, String word, int count) {
        int len = sb.length();
        if (word.length() == 0) {
            if (count != 0) sb.append(count);
            res.add(sb.toString());
        } else {
            // skip current char
            dfs(res, sb, word.substring(1), count + 1);
            // keep current char
            if (count != 0) sb.append(count);
            sb.append(word.charAt(0));
            dfs(res, sb, word.substring(1), 0);
        }
        sb.setLength(len);
    }
}