# 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 class Solution { public: vector generateAbbreviations(string word) { vector ans; dfs(word, 0, 0, {}, ans); return ans; } private: void dfs(const string& word, int i, int count, vector&& path, vector& 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& 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 generateAbbreviations(String word) { List 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 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) : ""; } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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