Skip to content

320. Generalized Abbreviation

  • Time: $O(2^n)$
  • Space: $O(2^n)$
 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
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  vector<string> generateAbbreviations(string word) {
    vector<string> ans;
    dfs(word, 0, 0, {}, ans);
    return ans;
  }

 private:
  void dfs(const string& word, int i, int count, vector<string>&& path,
           vector<string>& ans) {
    if (i == word.length()) {
      ans.push_back(join(path) + getCountString(count));
      return;
    }

    // Abbreviate the word[i].
    dfs(word, i + 1, count + 1, std::move(path), ans);
    // Keep the word[i], so consume the count as a string
    path.push_back(getCountString(count) + word[i]);
    // Reset the count to 0.
    dfs(word, i + 1, 0, std::move(path), ans);
    path.pop_back();
  }

  string getCountString(int count) {
    return count > 0 ? to_string(count) : "";
  }

  string join(const vector<string>& path) {
    string joined;
    for (const string& s : path)
      joined += s;
    return joined;
  };
};

 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
27
28
class Solution {
  public List<String> generateAbbreviations(String word) {
    List<String> ans = new ArrayList<>();
    dfs(word, 0, 0, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(final String word, int i, int count, StringBuilder sb, List<String> ans) {
    if (i == word.length()) {
      final int length = sb.length();
      ans.add(sb.append(getCountString(count)).toString());
      sb.setLength(length);
      return;
    }

    // Abbreviate the word[i].
    dfs(word, i + 1, count + 1, sb, ans);
    // Keep the word[i], so consume the count as a string.
    final int length = sb.length();
    // Reset the count to 0.
    dfs(word, i + 1, 0, sb.append(getCountString(count)).append(word.charAt(i)), ans);
    sb.setLength(length);
  }

  private String getCountString(int count) {
    return count > 0 ? String.valueOf(count) : "";
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def generateAbbreviations(self, word: str) -> list[str]:
    ans = []

    def getCountString(count: int) -> str:
      return str(count) if count > 0 else ''

    def dfs(i: int, count: int, path: list[str]) -> None:
      if i == len(word):
        ans.append(''.join(path) + getCountString(count))
        return

      # Abbreviate the word[i].
      dfs(i + 1, count + 1, path)
      # Keep the word[i], so consume the count as a string.
      path.append(getCountString(count) + word[i])
      # Reset the count to 0.
      dfs(i + 1, 0, path)
      path.pop()

    dfs(0, 0, [])
    return ans