Leetcode 320. Generalized Abbreviation

Problem Description

The task is to write a function, generateAbbreviations that generates all possible abbreviations for an input word. In the context of this problem, an abbreviation of a word is defined as a combination of the count of characters followed by a character from the word. We will add these abbreviations to a list and return it.

For instance:

If the input word is "word", some of the possible abbreviations are "1ord", "w1rd", "wo1d" and "wor1". We could also replace more than one consecutive characters with the count, resulting in abbreviations like "2rd", "w2d", "1o1d", etc.

The problem is tagged medium difficulty and is commonly presented in interviews with Google.

Approach

The solution uses a depth-first search (DFS) to generate the abbreviations. DFS is perfect for this problem as it naturally handles all possibilities by sequentially exploring each possible path in a recursive manner.

For each character in the word, we have the option to either abbreviate it or keep the original character. If we decide to abbreviate, the count of abbreviations increases by one. If we don't, we add any existing count to the solution as a string, followed by the original character, and reset the count to zero.

The base case for the recursion is reached when all characters in the word have been examined. At that point, we append the current set of abbreviations to the final list.

Worked Example

Suppose we have the word "ab". We start from the first character, "a". We either abbreviate it ("1") or keep it as it is ("a"). For both possibilities, we move to the second character, "b", where we again have the same options. We can abbreviate it (leading to "11" and "a1") or keep it as it (leading to "1b" and "ab").

Python Solution

1
2python
3class Solution:
4  def generateAbbreviations(self, word: str):
5        def dfs(i, curr, count):
6            if i == len(word):
7                result.append(curr + str(count) if count > 0 else curr)
8            else:
9                dfs(i + 1, curr, count + 1)  # abbreviate the current character
10                dfs(i + 1, curr + (str(count) if count != 0 else "") + word[i], 0)  # keep the current character
11
12        result = []
13        dfs(0, "", 0)
14        return result

Java Solution

1
2java
3public class Solution {
4    public List<String> generateAbbreviations(String word) {
5        List<String> result = new ArrayList<>();
6        dfs(result, new StringBuilder(), word.toCharArray(), 0, 0);
7        return result;
8    }
9
10    private void dfs(List<String> result, StringBuilder sb, char[] c, int i, int num) {
11        int len = sb.length();  // keep the old length
12        if (i == c.length) {
13            if (num != 0) sb.append(num);  // append the last number
14            result.add(sb.toString());
15        } else {
16            dfs(result, sb, c, i + 1, num + 1);  // abbr c[i]
17
18            if (num != 0) sb.append(num);  // append count
19            dfs(result, sb.append(c[i]), c, i + 1, 0);  // not abbr c[i]
20        }
21        sb.setLength(len);  // reset to the old length
22    }
23}

Javascript Solution

1
2javascript
3var generateAbbreviations = function(word) {
4    let answer = []
5    dfs(word, 0, 0, '', answer)
6    return answer
7};
8
9function dfs(word, i, count, cur, answer){
10    if (i === word.length){
11        if (count !== 0) cur += count
12        answer.push(cur)
13        return
14    }
15    dfs(word, i + 1, count + 1, cur, answer)
16    dfs(word, i + 1, 0, cur + (count > 0 ? count : '') + word[i], answer)
17}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<string> generateAbbreviations(string word) {
6        vector<string> res;
7        dfs(word, 0, 0, "", res);
8        return res;
9    }
10    
11    void dfs(string word, int i, int k, string newWord, vector<string>& res){
12        if(i==word.size()){
13            if(k != 0) newWord += to_string(k);
14            res.push_back(newWord);
15        } else {
16            dfs(word, i+1, k+1, newWord, res);  //abbreviate word[i];
17            dfs(word, i+1, 0, newWord + (k>0? to_string(k): "") + word[i], res); //keep word[i]
18        }    
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> GenerateAbbreviations(string word) {
5        IList<string> res = new List<string>();
6        DFS(res, "", word.ToCharArray(), 0, 0);
7        return res;
8    }
9    
10    private void DFS(IList<string> res, string str, char[] word, int i, int num) {
11        int len = str.Length;  
12        if(i == word.Length) {
13            if(num != 0) str += num;
14            res.Add(str);
15        } else {
16            DFS(res, str, word, i + 1, num + 1);  // abbreviate word[i]
17            DFS(res, str + (num > 0 ? num.ToString() : "") + word[i], word, i + 1, 0);  // keep word[i]
18        }
19    }
20}

With this approach, we can generate all possible abbreviations for a given word, using relatively few lines of code. Note that the solution does not guarantee the order of the output, as this is not a requirement in the problem statement.## Solution Complexity Analysis

The time complexity for the solutions above is O(2^n), where n is the length of the input word. This complexity results from the fact that, for each character in the input word, we are creating two recursive calls - one for the case where we abbreviate the character and another for the case where we don't.

To understand this a bit better, think of it as a binary tree, where each node splits into two branches, representing the two choices (to abbreviate or not). The height of this tree would be equal to the number of characters in the word, and so the total number of nodes (which corresponds to the total number of recursive calls we make) would be 2^n.

The space complexity is O(n) because in the worst-case scenario, if we consider the function call stack, we could end up with n recursive calls on the stack. Furthermore, we use a string or a StringBuilder to keep track of the current abbreviation. This string might contain all characters from the original word, resulting in a space usage proportional to n.

Please note that the output list storing all abbreviations is not taken into account while calculating the space complexity because the problem specifically requires the solution to generate all possible abbreviations, thus making the space needed for the output a necessity.

While the search space for this problem is high (2^n possible abbreviations), this solution is efficient in the sense that it doesn't perform any unnecessary work; each recursive call contributes to the output. It's also worth noting that these solutions are quite clean and concise. Using a general-purpose strategy like depth-first search allows us to solve the problem with relatively few lines of code.