[LintCode] Problem 779 - Generalized Abbreviation

Posted on | In ,

Write a function to generate the generalized abbreviations of a word.(order does not matter)

Example

No.1

Input:
word = “word”,

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

No.2

Input:
word = “today”

Output:
[“1o1a1”,”1o1ay”,”1o2y”,”1o3”,”1od1y”,”1od2”,”1oda1”,”1oday”,”2d1y”,”2d2”,”2da1”,”2day”,”3a1”,”3ay”,”4y”,”5”,”t1d1y”,”t1d2”,”t1da1”,”t1day”,”t2a1”,”t2ay”,”t3y”,”t4”,”to1a1”,”to1ay”,”to2y”,”to3”,”tod1y”,”tod2”,”toda1”,”today”]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<String> generateAbbreviations(String word) {
    List<String> result = new ArrayList<>();
    helper(result, word, 0, 0, new StringBuilder());
    return result;
}

private void helper(List<String> result, String word, int idx, int count, StringBuilder sb) {
    if (idx == word.length()) {
        if (count > 0)
            sb.append(count);

        result.add(sb.toString());
        return;
    }

    int length = sb.length();

    helper(result, word, idx + 1, count + 1, sb);

    sb.setLength(length);

    if (count > 0)
        helper(result, word, idx + 1, 0, sb.append(count).append(word.charAt(idx)));
    else
        helper(result, word, idx + 1, 0, sb.append(word.charAt(idx)));
}