Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Unique Generalized Abbreviations

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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']
A

Anonymous

· 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
A

Anonymous

· 4 years ago

Could you explain the meaning of the start and count attributes?

Reading Progress

0%

Vote for new content