320. Generalized Abbreviation

MediumBit ManipulationStringBacktracking
Leetcode Link

Problem Description

The problem asks us to generate all possible generalized abbreviations for a given word. A generalized abbreviation for a word is a transformation where any number of non-overlapping and non-adjacent substrings can be replaced with their respective lengths. The key points to remember are:

  • Substrings that we replace with numbers must not overlap with each other.
  • Substrings that we replace must not be adjacent.
  • We can use the whole word as a substring, which means the entire word can be replaced with a single number indicating its length.
  • The returned list does not need to be in any specific order.

To understand it better, let's look at an example with the word "abc". Possible generalized abbreviations for "abc" include "abc" (no change), "1bc" (replacing "a" with "1"), "a2" (replacing "bc" with "2"), "ab1" (replacing "c" with "1"), "1b1" (replacing the first and last characters with "1"), and "3" (replacing the entire word with "3").

Intuition

The process to solve this problem can be approached using recursion and backtracking. We can think of each character in the word as a decision point: at each character, we can decide to:

  • Replace a substring starting at this character with a number that represents its length.
  • Skip the character to keep it as is.

While performing these operations, we must ensure that we are not violating the rules of replacing non-overlapping and non-adjacent substrings. Therefore, each time we replace a substring with its length, we skip the next character to maintain the non-adjacency condition.

To arrive at the solution, we start by writing a recursive function that can generate the aforementioned abbreviations by considering each character. This function should have the ability to record the current state (as an abbreviation in progress) and be able to backtrack to explore different abbreviation possibilities until all possibilities have been exhausted.

The algorithm works as follows:

  1. At each recursion level, the function is given the remaining string to process and the current abbreviation state.
  2. If the remaining string is empty, the current state is one of the solutions, so add it to the answer list.
  3. For each possible length of the substring to be abbreviated (from 1 to the length of the remaining string):
    • Append the length number to the current state.
    • If there are characters remaining after the substring, append the next character to enforce non-adjacency, and recurse with the remaining string after this character.
    • Backtrack: remove the added elements from the current state to explore other abbreviation possibilities.
  4. Also, consider keeping the current character as is and recurse with the remaining string after this character.

The solution to the problem emerges as we systematically explore each abbreviation possibility while adhering to the established rules.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The implemented solution uses depth-first search (DFS) and backtracking to generate all possible generalized abbreviations of the input word. The code defines a recursive function dfs that accepts the remaining string s to process and a temporary list t which keeps track of the current abbreviation being constructed.

Here is a step-by-step walkthrough of the implementation:

  1. Base Case: If the remaining string s is empty, it means we have reached the end of the string and have constructed a valid abbreviation. Hence, we join the elements in the temporary list t into a string and append it to ans, the final list of abbreviations.

  2. Recursive Case:

    • We iterate over the range from 1 to len(s) + 1 which represents the length of the substring we are considering for replacement.
    • For each length i, we have two cases to consider:
      • Abbreviation: We append the length i to t as a substring replacement. If i is less than the length of s, we also append the next character to t (to satisfy the non-adjacency condition) and then recursively call dfs with the remaining string s[i+1:]. After the recursive call, we backtrack by popping the added elements from t.
      • No Abbreviation (End of Recursion): If the length i is equal to the length of s, we simply perform a recursive call without adding any more characters, as we would be considering the entire remaining string as one substring.
    • Additionally, we must consider the case where we do not replace the current character with its abbreviation. Therefore, we append the current character s[0] to t and recursively call dfs with s[1:]. We backtrack by popping the character after recursion.

The choice of algorithm and data structure:

  • Depth-First Search (DFS): Used to explore all possible abbreviation combinations by diving deeper into the recursive tree structure based on the decisions made (to replace or not to replace substrings).
  • Backtracking: Used to undo the decision at each step (once all possibilities after that decision are explored) to backtrack and explore other paths in the decision tree.
  • Temporary List (t): It keeps track of the current state of the abbreviation and is modified in place during recursion to save space.
  • Final List (ans): Used to store all the possible abbreviation combinations generated.

Here is the code excerpt that illustrates the recursive approach:

1def dfs(s, t):
2    if not s:
3        ans.append(''.join(t))
4        return
5    for i in range(1, len(s) + 1):
6        t.append(str(i))
7        if i < len(s):
8            t.append(s[i])
9            dfs(s[i + 1:], t)
10            t.pop()  # Backtrack
11        else:
12            dfs(s[i:], t)  # End of Recursion
13        t.pop()  # Backtrack
14    t.append(s[0])
15    dfs(s[1:], t)
16    t.pop()  # Backtrack

The function generateAbbreviations initializes the final answer ans and calls dfs with the initial word and an empty temporary list to start the process. After all the possible abbreviations are generated, the ans list is returned.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's assume our given word is "word". We use the recursive implementation of the solution approach to generate all possible generalized abbreviations. We'll use a step-by-step walk through to illustrate how the algorithm works.

First, we call the dfs function with the full string "word" and an empty temporary list t.

  1. In the first level of recursion, s is "word".

    • We consider all lengths of substrings starting from 1 to the length of "word".

    a. Length 1: We replace "w" with "1". - Temp list t becomes ["1"]. - We call dfs with the remaining string "ord" and t as ["1", "o"] (enforcing non-adjacency). - This recursion continues, similarly replacing one character at a time and enforcing non-adjacency, until the base case is reached and the possible abbreviations like "1o2", "1or1", and "1ord" are added to ans.

    b. Length 2: We replace "wo" with "2". - Temp list t becomes ["2"]. - We call dfs with the remaining string "rd" and t as ["2", "r"] (enforcing non-adjacency). - Following the similar pattern, "2r1" and "2rd" are added to ans.

    c. This pattern continues for length 3 and 4, adding "3d" and "4" respectively to ans.

  2. Additionally, we have the option to keep "w" as is and recurse with the remaining string "ord".

    • Temp list t is ["w"].
    • This recursion follows the same pattern as before, exploring all options with the prefix "w" and generating abbreviations like "w1r1", "w2", "wo1d", "wor1", and "word".

These steps will systematically continue for each possibility, exploring further branches in the recursion tree and using backtracking to generate all possible abbreviations. Once all recursion paths are explored, we have our complete list ans with all generated generalized abbreviations. The recursive calls ensure that we don't create overlapping abbreviations and that no two numbers are adjacent, maintaining the problem's constraints.

The final output for the given word "word" will hence include entries like "word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "3d", "w3", and "4", among others.

Not Sure What to Study? Take the 2-min Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Python Solution

1class Solution:
2    def generateAbbreviations(self, word: str) -> List[str]:
3        # Helper function to perform depth-first search to find all possible abbreviations
4        def dfs(remaining, current_abbreviation):
5            if not remaining:
6                # No more characters left to abbreviate, add the current abbreviation to answers
7                answers.append(''.join(current_abbreviation))
8                return
9          
10            # Consider abbreviation for every possible length starting from each index
11            for i in range(1, len(remaining) + 1):
12                # Append the number (length of abbreviation)
13                current_abbreviation.append(str(i))
14              
15                # If there are characters remaining, append the next character after abbreviation
16                if i < len(remaining):
17                    current_abbreviation.append(remaining[i])
18                    dfs(remaining[i + 1:], current_abbreviation)
19                    # Backtrack to previous state
20                    current_abbreviation.pop()
21                else:
22                    # All characters are abbreviated, call dfs with an empty remaining string
23                    dfs(remaining[i:], current_abbreviation)
24              
25                # Backtrack to consider next abbreviation possibility
26                current_abbreviation.pop()
27          
28            # Consider not abbreviating the first character and recursively find further abbreviations
29            current_abbreviation.append(remaining[0])
30            dfs(remaining[1:], current_abbreviation)
31            # Backtrack after exploring abbreviations with the first character included
32            current_abbreviation.pop()
33
34        answers = []  # List to store all possible abbreviations
35        dfs(word, [])  # Start the depth-first search with the full word and empty current abbreviation
36        return answers
37

Java Solution

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    // Class variable to store the final list of abbreviations.
6    private List<String> abbreviations;
7
8    // Public method that initiates the generation of abbreviations for a word.
9    public List<String> generateAbbreviations(String word) {
10        abbreviations = new ArrayList<>();
11      
12        // Temporary list to keep track of current abbreviation progression.
13        List<String> currentAbbreviation = new ArrayList<>();
14      
15        // Start the depth first search (DFS) from the beginning of the word.
16        dfs(word, currentAbbreviation);
17      
18        // Return the list of all possible abbreviations after DFS is complete.
19        return abbreviations;
20    }
21
22    // Helper method to perform depth first search to generate all abbreviations.
23    private void dfs(String remainingSubstring, List<String> currentAbbreviation) {
24        // If the remaining substring is empty, join all collected parts and add to result.
25        if ("".equals(remainingSubstring)) {
26            abbreviations.add(String.join("", currentAbbreviation));
27            return;
28        }
29      
30        // Try all possible lengths of numbers to abbreviate (up to the length of the remaining substring).
31        for (int i = 1; i <= remainingSubstring.length(); ++i) {
32            // Add number abbreviation for the current length.
33            currentAbbreviation.add(Integer.toString(i));
34          
35            // If there are characters left, add the next character and continue DFS.
36            if (i < remainingSubstring.length()) {
37                currentAbbreviation.add(String.valueOf(remainingSubstring.charAt(i)));
38                dfs(remainingSubstring.substring(i + 1), currentAbbreviation);
39              
40                // Backtracking - remove the last character to explore new paths.
41                currentAbbreviation.remove(currentAbbreviation.size() - 1);
42            } else {
43                // If no characters are left, continue DFS with the current abbreviation.
44                dfs(remainingSubstring.substring(i), currentAbbreviation);
45            }
46          
47            // Backtracking - remove the number abbreviation to try a different abbreviation length.
48            currentAbbreviation.remove(currentAbbreviation.size() - 1);
49        }
50      
51        // Try keeping the first character as is and continue DFS for the rest of the string.
52        currentAbbreviation.add(String.valueOf(remainingSubstring.charAt(0)));
53        dfs(remainingSubstring.substring(1), currentAbbreviation);
54      
55        // Backtracking - remove the character to keep the path tree clean for new paths.
56        currentAbbreviation.remove(currentAbbreviation.size() - 1);
57    }
58}
59

C++ Solution

1#include <vector>
2#include <string>
3
4using namespace std;
5
6class Solution {
7private:
8    vector<string> abbreviations; // Vector to store the final list of abbreviations.
9
10    // Helper method to perform depth-first search to generate all abbreviations.
11    void dfs(const string& remainingSubstring, vector<string>& currentAbbreviation) {
12        // If the remaining substring is empty, concatenate all collected parts and add to the result.
13        if (remainingSubstring.empty()) {
14            abbreviations.push_back(join(currentAbbreviation, ""));
15            return;
16        }
17      
18        // Try all possible lengths of numbers to abbreviate (up to the length of the remaining substring).
19        for (int i = 1; i <= remainingSubstring.size(); ++i) {
20            // Add number abbreviation for the current length.
21            currentAbbreviation.push_back(to_string(i));
22          
23            // If there are characters left, add the next character and continue DFS.
24            if (i < remainingSubstring.size()) {
25                currentAbbreviation.push_back(string(1, remainingSubstring[i]));
26                dfs(remainingSubstring.substr(i + 1), currentAbbreviation);
27              
28                // Backtracking - remove the last character to explore new paths.
29                currentAbbreviation.pop_back();
30            } else {
31                // If no characters are left, continue DFS with the current abbreviation.
32                dfs(remainingSubstring.substr(i), currentAbbreviation);
33            }
34          
35            // Backtracking - remove the number abbreviation to try a different abbreviation length.
36            currentAbbreviation.pop_back();
37        }
38      
39        // Try keeping the first character as is and continue DFS for the rest of the string.
40        currentAbbreviation.push_back(string(1, remainingSubstring[0]));
41        dfs(remainingSubstring.substr(1), currentAbbreviation);
42      
43        // Backtracking - remove the character to keep the path tree clean for new paths.
44        currentAbbreviation.pop_back();
45    }
46
47    // Helper method to join strings in a vector into a single string with a given delimiter.
48    string join(const vector<string>& parts, const string& delimiter) {
49        string result;
50      
51        // Iterating over each part and appending to the result string.
52        for (const auto& part : parts) {
53            if (&part != &parts[0]) { // Avoid adding delimiter before the first element.
54                result += delimiter;
55            }
56            result += part;
57        }
58        return result;
59    }
60
61public:
62    // Public method that initiates the generation of abbreviations for a word.
63    vector<string> generateAbbreviations(const string& word) {
64        abbreviations.clear();
65      
66        // Temporary vector to keep track of the current abbreviation progression.
67        vector<string> currentAbbreviation;
68      
69        // Start the depth-first search (DFS) from the beginning of the word.
70        dfs(word, currentAbbreviation);
71      
72        // Return the vector of all possible abbreviations after DFS is complete.
73        return abbreviations;
74    }
75};
76

Typescript Solution

1// Global variable to store the final list of abbreviations.
2let abbreviations: string[] = [];
3
4// Function that initiates the generation of abbreviations for a word.
5function generateAbbreviations(word: string): string[] {
6    abbreviations = [];
7  
8    // Temporary array to keep track of current abbreviation progression.
9    let currentAbbreviation: string[] = [];
10  
11    // Start the depth-first search (DFS) from the beginning of the word.
12    dfs(word, currentAbbreviation);
13  
14    // Return the list of all possible abbreviations after DFS is complete.
15    return abbreviations;
16}
17
18// Helper function to perform depth-first search to generate all abbreviations.
19function dfs(remainingSubstring: string, currentAbbreviation: string[]): void {
20    // If the remaining substring is empty, join all collected parts and add to the result.
21    if (remainingSubstring === "") {
22        abbreviations.push(currentAbbreviation.join(""));
23        return;
24    }
25  
26    // Try all possible lengths of numbers to abbreviate (up to the length of the remaining substring).
27    for (let i = 1; i <= remainingSubstring.length; i++) {
28        // Add number abbreviation for the current length.
29        currentAbbreviation.push(i.toString());
30      
31        // If there are characters left, add the next character and continue DFS.
32        if (i < remainingSubstring.length) {
33            currentAbbreviation.push(remainingSubstring.charAt(i));
34            dfs(remainingSubstring.substring(i + 1), currentAbbreviation);
35          
36            // Backtracking - remove the last character to explore new paths.
37            currentAbbreviation.pop();
38        } else {
39            // If no characters are left, continue DFS with the current abbreviation.
40            dfs("", currentAbbreviation);
41        }
42      
43        // Backtracking - remove the number abbreviation to try a different abbreviation length.
44        currentAbbreviation.pop();
45    }
46  
47    // Try keeping the first character as is and continue DFS for the rest of the string.
48    currentAbbreviation.push(remainingSubstring.charAt(0));
49    dfs(remainingSubstring.substring(1), currentAbbreviation);
50  
51    // Backtracking - remove the character to keep the path tree clean for new paths.
52    currentAbbreviation.pop();
53}
54
Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

The time complexity of this code can be analyzed by considering the number of different abbreviation combinations that can be generated for a word of length n. At every character position in the word, we have two choices: abbreviate by using a number or use the character itself. This results in a recursion tree with a maximum branch factor of n, as we can abbreviate up to n characters in one go, forming a sequence of overlapping subproblems. Therefore, the time complexity is O(2^n) since the recursion depth is n and at every level we are making two choices. However, because of the way the abbreviations are generated (with numbers that can represent multiple characters), the actual time complexity is less strictly bounded and is dependent on the structure of the recursion.

The space complexity is determined by the depth of the recursion stack and the space required to store the intermediate strings. In the worst case, the recursion depth is n and the intermediate strings can also be of length n, leading to a space complexity of O(n).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫