Generalized Abbreviation

Description

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

Hint

Train of Thought

The idea is: for every character, we can keep it or abbreviate it. To keep it, we add it to the current solution and carry on backtracking. To abbreviate it, we omit it in the current solution, but increment the count, which indicates how many characters have we abbreviated. When we reach the end or need to put a character in the current solution, and count is bigger than zero, we add the number into the solution.

(1) use StringBuilder rather than the concatenation of String. (2) use char[] to represent String rather than the original String.

Code

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        StringBuilder tmpRes = new StringBuilder();
        char[] wordArray = word.toCharArray();
        dfs(res, tmpRes, wordArray, 0, 0);
        return res;
    }

    private void dfs(List<String> res, StringBuilder tmpRes, char[] wordArray, int pos, int numCount) {
        if(pos == wordArray.length) {
            if(numCount > 0) tmpRes.append(numCount);
            res.add(tmpRes.toString());
            return;
        }

        // use number
        int len = tmpRes.length();
        dfs(res, tmpRes, wordArray, pos + 1, numCount + 1);
        tmpRes.setLength(len);              // backtracking

        // use character
        len = tmpRes.length();
        if(numCount > 0) {
            tmpRes.append(numCount).append(wordArray[pos]);
            dfs(res, tmpRes, wordArray, pos + 1, 0);    
        } else {
            tmpRes.append(wordArray[pos]);
            dfs(res, tmpRes, wordArray, pos + 1, 0);
        }
        tmpRes.setLength(len);              // backtracking
    }
}

Complexity