Generalized Abbreviation

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

Tips:

Backtracking，关键是string的某一位char缩写还是不缩写

就是用dfs把每一位缩写和不缩写的所有情况遍历出来，缩写就变数字撒，然后变之前检查前一位是不是数字，前一位是数字就合并数字

方法2：

For each char c[i], either abbreviate it or not.

Abbreviate: count accumulate num of abbreviating chars, but don't append it yet.
Not Abbreviate: append accumulated num as well as current char c[i].
In the end append remaining num.
Using StringBuilder can decrease 36.4% time.
This comes to the pattern I find powerful:
int len = sb.length(); // decision point
... backtracking logic ...
sb.setLength(len);     // reset to decision point
Similarly, check out remove parentheses and add operators.

Code:

    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        if (word == null || word.length() == 0) {
            result.add("");
            return result;
        }
        helper(result, word, new StringBuilder(), 0);
        return result;
    }
    private void helper(List<String> result, String word, StringBuilder build, int index) {
        if (index == word.length()) {
            result.add(build.toString());
            return;
        }
        String copy = build.toString();
        if (build.length() > 0 && build.charAt(build.length() - 1) >= '0' && (build.charAt(build.length() - 1) <= '9')) {
            char previous = build.charAt(build.length() - 1);
            if (previous == '9') {
                build.setCharAt(build.length() - 1, '1');
                build.append('0');
            }
            else build.setCharAt(build.length() - 1, (char)(previous + 1));
        }
        else {
            build.append('1');
        }
        helper(result, word, build, index + 1);
        build = new StringBuilder(copy);
        build.append(word.charAt(index));
        helper(result, word, build, index + 1);
    }

解法2：

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

    public void DFS(List<String> res, StringBuilder sb, char[] c, int i, int num) {
        int len = sb.length();  
        if(i == c.length) {
            if(num != 0) sb.append(num);
            res.add(sb.toString());
        } else {
            DFS(res, sb, c, i + 1, num + 1);               // abbr c[i]

            if(num != 0) sb.append(num);                   // not abbr c[i]
            DFS(res, sb.append(c[i]), c, i + 1, 0);        
        }
        //sb.setLength(len); 
        if(sb.length() > 0) {
            sb.delete(len, sb.length());
        }
    }
}