320 Generalized Abbreviation

320. Generalized Abbreviation​
1. Question
Write a function to generate the generalized abbreviations of a word.
Example:
Given word ="word", return the following list (order does not matter):
1
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Copied!
2. Implementation
(1) Backtracking
1
class Solution {
2
    public List<String> generateAbbreviations(String word) {
3
        List<String> res = new ArrayList<>();
4
​
5
        getAbbreviations(word, 0, 0, "", res);
6
        return res;
7
    }
8
​
9
    public void getAbbreviations(String word, int pos, int count, String curStr, List<String> res) {
10
        if (pos == word.length()) {
11
            if (count > 0) {
12
                curStr += count;
13
            }
14
            res.add(curStr);
15
            return;
16
        }
17
​
18
        // Abbreviate the current character
19
        getAbbreviations(word, pos + 1, count + 1, curStr, res);
20
        // Keep the current character
21
        getAbbreviations(word, pos + 1, 0, curStr + (count > 0 ? count : "") + word.charAt(pos), res);
22
    }
23
 }
Copied!
3. Time & Space Complexity
Backtracking: 时间复杂度O(2^n), 空间复杂度O(2^n)

291 Word Pattern II

351 Android Unlock Patterns

Last modified 2yr ago

Copy link

Contents

320. Generalized Abbreviation

1. Question

2. Implementation

3. Time & Space Complexity

320. Generalized Abbreviation​

1. Question

2. Implementation

3. Time & Space Complexity

320. Generalized Abbreviation