Welcome to Subscribe On Youtube
320. Generalized Abbreviation
Description
A word's generalized abbreviation can be constructed by taking any number of nonoverlapping and nonadjacent substrings and replacing them with their respective lengths.
 For example,
"abcde"
can be abbreviated into:"a3e"
("bcd"
turned into"3"
)"1bcd1"
("a"
and"e"
both turned into"1"
)"5"
("abcde"
turned into"5"
)"abcde"
(no substrings replaced)
 However, these abbreviations are invalid:
"23"
("ab"
turned into"2"
and"cde"
turned into"3"
) is invalid as the substrings chosen are adjacent."22de"
("ab"
turned into"2"
and"bc"
turned into"2"
) is invalid as the substring chosen overlap.
Given a string word
, return a list of all the possible generalized abbreviations of word
. Return the answer in any order.
Example 1:
Input: word = "word" Output: ["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]
Example 2:
Input: word = "a" Output: ["1","a"]
Constraints:
1 <= word.length <= 15
word
consists of only lowercase English letters.
Solutions
Solution 1: DFS
We design a function $dfs(i)$, which returns all possible abbreviations for the string $word[i:]$.
The execution logic of the function $dfs(i)$ is as follows:
If $i \geq n$, it means that the string $word$ has been processed, and we directly return a list composed of an empty string.
Otherwise, we can choose to keep $word[i]$, and then add $word[i]$ to the front of each string in the list returned by $dfs(i + 1)$, and add the obtained result to the answer.
We can also choose to delete $word[i]$ and some characters after it. Suppose we delete $word[i..j)$, then the $j$ th character is not deleted, and then add $j  i$ to the front of each string in the list returned by $dfs(j + 1)$, and add the obtained result to the answer.
Finally, we call $dfs(0)$ in the main function.
The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $word$.
Solution 2: Binary Enumeration
Since the length of the string $word$ does not exceed $15$, we can use the method of binary enumeration to enumerate all abbreviations. We use a binary number $i$ of length $n$ to represent an abbreviation, where $0$ represents keeping the corresponding character, and $1$ represents deleting the corresponding character. We enumerate all $i$ in the range of $[0, 2^n)$, convert it into the corresponding abbreviation, and add it to the answer list.
The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $word$.

class Solution { public List<String> generateAbbreviations(String word) { int n = word.length(); List<String> ans = new ArrayList<>(); for (int i = 0; i < 1 << n; ++i) { StringBuilder s = new StringBuilder(); int cnt = 0; for (int j = 0; j < n; ++j) { if ((i >> j & 1) == 1) { ++cnt; } else { if (cnt > 0) { s.append(cnt); cnt = 0; } s.append(word.charAt(j)); } } if (cnt > 0) { s.append(cnt); } ans.add(s.toString()); } return ans; } }

class Solution { public: vector<string> generateAbbreviations(string word) { int n = word.size(); vector<string> ans; for (int i = 0; i < 1 << n; ++i) { string s; int cnt = 0; for (int j = 0; j < n; ++j) { if (i >> j & 1) { ++cnt; } else { if (cnt) { s += to_string(cnt); cnt = 0; } s.push_back(word[j]); } } if (cnt) { s += to_string(cnt); } ans.push_back(s); } return ans; } };

class Solution: def generateAbbreviations(self, word: str) > List[str]: n = len(word) ans = [] for i in range(1 << n): cnt = 0 s = [] for j in range(n): if i >> j & 1: cnt += 1 else: if cnt: s.append(str(cnt)) cnt = 0 s.append(word[j]) if cnt: s.append(str(cnt)) ans.append("".join(s)) return ans

func generateAbbreviations(word string) (ans []string) { n := len(word) for i := 0; i < 1<<n; i++ { s := &strings.Builder{} cnt := 0 for j := 0; j < n; j++ { if i>>j&1 == 1 { cnt++ } else { if cnt > 0 { s.WriteString(strconv.Itoa(cnt)) cnt = 0 } s.WriteByte(word[j]) } } if cnt > 0 { s.WriteString(strconv.Itoa(cnt)) } ans = append(ans, s.String()) } return }

function generateAbbreviations(word: string): string[] { const n = word.length; const ans: string[] = []; for (let i = 0; i < 1 << n; ++i) { const s: string[] = []; let cnt = 0; for (let j = 0; j < n; ++j) { if ((i >> j) & 1) { ++cnt; } else { if (cnt > 0) { s.push(cnt.toString()); cnt = 0; } s.push(word[j]); } } if (cnt > 0) { s.push(cnt.toString()); } ans.push(s.join('')); } return ans; }