Skip to content

320. Generalized Abbreviation πŸ”’

DifficultyMedium

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:
    • "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

Thinking

Each letter is kept or folded into a run of omitted counts. \(n\le 15\), so every scheme is enumerable.

\(dfs(i)\) handles the suffix: keep \(word[i]\) and recurse, or collapse \([i,j)\) into a number and append \(word[j]\) (if any) plus the rest. The empty suffix returns \([""]\) as the join base.

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

Thinking

The recursion matches the \(2^n\) keep/omit choices. A bit mask marks omitted positions; runs of \(1\)s become a count, a \(0\) emits the letter. The iterative form drops the call stack.

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
}

Comments