Description#
A word's generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent substrings and replacing them with their respective lengths.
- For example,
"abcde" can be abbreviated into:<ul>
<li><code>"a3e"</code> (<code>"bcd"</code> turned into <code>"3"</code>)</li>
<li><code>"1bcd1"</code> (<code>"a"</code> and <code>"e"</code> both turned into <code>"1"</code>)</li>
<li><code>"5"</code> (<code>"abcde"</code> turned into <code>"5"</code>)</li>
<li><code>"abcde"</code> (no substrings replaced)</li>
</ul>
</li>
<li>However, these abbreviations are <strong>invalid</strong>:
<ul>
<li><code>"23"</code> (<code>"ab"</code> turned into <code>"2"</code> and <code>"cde"</code> turned into <code>"3"</code>) is invalid as the substrings chosen are adjacent.</li>
<li><code>"22de"</code> (<code>"ab"</code> turned into <code>"2"</code> and <code>"bc"</code> turned into <code>"2"</code>) is invalid as the substring chosen overlap.</li>
</ul>
</li>
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 <= 15word 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$.
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
def dfs(i: int) -> List[str]:
if i >= n:
return [""]
ans = [word[i] + s for s in dfs(i + 1)]
for j in range(i + 1, n + 1):
for s in dfs(j + 1):
ans.append(str(j - i) + (word[j] if j < n else "") + s)
return ans
n = len(word)
return dfs(0)
|
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
| class Solution {
private String word;
private int n;
public List<String> generateAbbreviations(String word) {
this.word = word;
n = word.length();
return dfs(0);
}
private List<String> dfs(int i) {
if (i >= n) {
return List.of("");
}
List<String> ans = new ArrayList<>();
for (String s : dfs(i + 1)) {
ans.add(String.valueOf(word.charAt(i)) + s);
}
for (int j = i + 1; j <= n; ++j) {
for (String s : dfs(j + 1)) {
ans.add((j - i) + "" + (j < n ? String.valueOf(word.charAt(j)) : "") + s);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<string> generateAbbreviations(string word) {
int n = word.size();
function<vector<string>(int)> dfs = [&](int i) -> vector<string> {
if (i >= n) {
return {""};
}
vector<string> ans;
for (auto& s : dfs(i + 1)) {
string p(1, word[i]);
ans.emplace_back(p + s);
}
for (int j = i + 1; j <= n; ++j) {
for (auto& s : dfs(j + 1)) {
string p = j < n ? string(1, word[j]) : "";
ans.emplace_back(to_string(j - i) + p + s);
}
}
return ans;
};
return dfs(0);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func generateAbbreviations(word string) []string {
n := len(word)
var dfs func(int) []string
dfs = func(i int) []string {
if i >= n {
return []string{""}
}
ans := []string{}
for _, s := range dfs(i + 1) {
ans = append(ans, word[i:i+1]+s)
}
for j := i + 1; j <= n; j++ {
for _, s := range dfs(j + 1) {
p := ""
if j < n {
p = word[j : j+1]
}
ans = append(ans, strconv.Itoa(j-i)+p+s)
}
}
return ans
}
return dfs(0)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function generateAbbreviations(word: string): string[] {
const n = word.length;
const dfs = (i: number): string[] => {
if (i >= n) {
return [''];
}
const ans: string[] = [];
for (const s of dfs(i + 1)) {
ans.push(word[i] + s);
}
for (let j = i + 1; j <= n; ++j) {
for (const s of dfs(j + 1)) {
ans.push((j - i).toString() + (j < n ? word[j] : '') + s);
}
}
return ans;
};
return dfs(0);
}
|
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$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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
|
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
| 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;
}
}
|
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
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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
}
|
