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_char and not next_char.isalpha()): 
      continue 

    if prev_char and not prev_char.isalpha(): # combine cur char and prev into one num
      new_abbrev = abbrev[:i-1] + str(int(prev_char) + 1) + abbrev[i+1:]
    elif next_char and not next_char.isalpha():
      new_abbrev = abbrev[:i] + str(int(next_char) + 1) + abbrev[i+2:]
    else:
      new_abbrev = abbrev[:i] + '1' + abbrev[i+1:]

    queue.append(new_abbrev)   
return result

""""