320. Generalized Abbreviation 🔒

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

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\).

Python3JavaC++GoTypeScript

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)

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;
    }
}

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);
    }
};

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)
}

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.