Unique Generalized Abbreviations (hard)

Problem Statement

Given a word, write a function to generate all of its unique generalized abbreviations.

A generalized abbreviation of a word can be generated by replacing each substring of the word with the count of characters in the substring. Take the example of “ab” which has four substrings: “”, “a”, “b”, and “ab”. After replacing these substrings in the actual word by the count of characters, we get all the generalized abbreviations: “ab”, “1b”, “a1”, and “2”.

Note: All contiguous characters should be considered one substring, e.g

.....

Like the course? Get enrolled and start learning!

Dylan Asoh

· 4 years ago

Ike Nwankwo

· 3 years ago

Here is my solution which is still O(N2^N) i believe. Only downside is It does process some values twice but asymptotically it should be the same as the given solution. I think mine is a little easier to understand as well.

""""

from collections import deque

class Solution: def generateGeneralizedAbbreviation(self, word): result = set() queue = deque([word]) while queue: abbrev = queue.popleft() result.add(abbrev) for i in range(len(abbrev)): char = abbrev[i] next_char = None if i + 1 == len(abbrev) else abbrev[i+1] prev_char = None if i == 0 else abbrev[i-1]

    if not char.isalpha(): continue # only evalute letters

    # dont evalute if surround by numbers
    if (prev_char and not prev_char.isalpha()) and (next_c

Show 1 reply

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def generateGeneralizedAbbreviation(self, word):
    
    # converts array with characters/numbers to string [1, 1, 'T']  --> 2T or ['A', 1, 'T'] --> A1T
    def arr_to_str(path):
      temp = []
      add = 0
      for char in path:
        if char == 1:
          add += 1
        else:
          if add > 0:
            temp.append(str(add))
            temp.append(char)
            add = 0 
          else:
            temp.append(char)
      if add > 0:
        temp.append(str(add))
      return ''.join(temp)

    '''
    The idea to covert the original string to an array and replace each permutation of characters with 1 
    Then use arr_to_str function to append to the result
    BAT == >
      ['B', 'A', 'T']
      [1, 'A', 'T']
      [1, 1, 'T']

Debasis B

· 2 years ago

    List<string> result = new List<string>();
    public List<string> generateGeneralizedAbbreviation(string word)
    {
        // Begin process
        generate(word, 0, new List<char>());
        // coalesce contiguous spaces to count of spaces
        processResult();
        return result;
    }

    private void processResult()
    {
        for (int i = 0; i < result.Count; i++)
        {
            result[i] = processResult(result[i]);
        }
    }

    private string processResult(string result)
    {
        Stack<char> chars = new Stack<char>();
        for (int i = 0; i < result.Length; i++)
        {
            if (result[i] == ' ')
            {
                // if top is digit: pop, increment and put back otherwise push 1
                if (chars.TryPee