LeetCode Solutions

Time: $O(2^n)$

Space: $O(2^n)$

			

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 word[i]
    dfs(word, i + 1, count + 1, move(path), ans);
    // Keep word[i], so consume the count as a string
    path.push_back(getCountString(count) + word[i]);
    dfs(word, i + 1, 0, move(path), ans);  // Reset count to 0
    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;
  };
};

			

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 word.charAt(i)
    dfs(word, i + 1, count + 1, sb, ans);
    // Keep word.charAt(i), so consume the count as a string
    final int length = sb.length();
    // Reset 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) : "";
  }
}

			

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 word[i]
      dfs(i + 1, count + 1, path)
      # Keep word[i], so consume the count as a string
      path.append(getCountString(count) + word[i])
      dfs(i + 1, 0, path)  # Reset count to 0
      path.pop()

    dfs(0, 0, [])
    return ans