getPhoneNumWords

getPhoneNumWords

"""

PROBLEM:

  4-digit number:  2284
  - assume have dictionary isWord(String word)
  - assume have phonenum pad digit to set of letters
  - print all possible words of ANY length up to 4-digits 
  
  eg 2->A,B,C   
     2284-> A, CAT, BAT, ACT, BATH

"""

"""

SOLUTION: 
 
 - decision-tree with 
   - digit spot at each LEVEL
   - possible letters on phone pad for digit at each BRANCH
 - BREADTH-SEARCH WITHIN specific LEVEL WITH
 - DEPTH-FIRST-SEARCH to 4th digit LEAF-LEVEL
 - PERMITs intermediate (non-leaf) results also!
 - recurse with backtracking to permit trial-attempts on nary-tree DFS!

*** DEBUG:
  - START of function and loop
  - rollback TRIAL state for NEXT loop iteration, or NEXT function BACKTRACK UP stack!
"""
import sys

def findWords(origPhoneNum, currentDigit, buildingWord):

  # print("RECURSE-LEVEL CALL ENTRY {}, {}, {}".format(origPhoneNum, currentDigit, buildingWord))
  
  # ATTN:  initialize cross-recurse-level and within-loop-level results!
  isWordFoundAtLevel = False
  isWordFoundAtDeeperLevel = False
    
  # validate current digit
  if (currentDigit < 0) or (currentDigit >= len(origPhoneNum)):
    raise ValueError("Error:  currentDigit must be within range of origPhoneNum!")
  
  # for all possible letter-choice branches for digit
  maxLen = len(origPhoneNum)

  lettersForDigit = digitToLetters[origPhoneNum[currentDigit]]
  for aLetter in lettersForDigit:
    
    buildingWord.append(aLetter)
    # convert back to string to lookup, reference
    localTestWordStr = ''.join(buildingWord)
    # print("WITHIN-LEVEL TOP LOOP {}".format(localTestWordStr))
    
    # INTERMEDIATE result; but do NOT break out of loop or RECURSION
    # as we care about words of 
    # ANY length, and we are still in LEVEL-LOOP!
    if localTestWordStr in realWords:
      isWordFoundAtLevel = True
      print("FOUND A WORD:  {}".format(localTestWordStr))
    
    if ((currentDigit + 1) < maxLen):
      # BUGFIX:
      # allow further RECURSION to LEAF level for LONGER word test 
      # REGARDLESS of if shorter localTestWordStr is a real word
      # increment DEPTH as we want words of ANY length UP TO maxLen!
      currentDigit += 1
      isWordFoundAtDeeperLevel = findWords(origPhoneNum, currentDigit, buildingWord)
      # BUGFIX:  BACKOUT prior DEPTH trial on THIS level LOOP for REMAINING letter in
      #          loop and do it immediately AFTER recursion which MUST be within loop 
      #          based on N-branches!
      currentDigit -= 1
    else:
      # bypass deeper recursion for this one element at MAX depth, 
      # but maintain currentDigit depth and buildingWord for REST of BREADTH LOOP
      pass
    
    # BUGFIX:  BACKOUT prior letter trial word at CURRENT BREADTH-LEVEL LOOP 
    # as GLOBAL SHARED MUTABLE buildingWord!  Need this to work for NEXT letter-branch!
    if buildingWord:
      backoutTrialLetter = buildingWord.pop()

  
  # BUGFIX:  
  # - TERMINATE recursion DEPTH only AFTER finished with BREADTH LOOP AND at MAX DEPTH!
  # - HOWEVER, MAX DEPTH would be taken care of by condition 
  #   PRIOR to recursion call within the loop anyway
  # - DEFAULT is to return result after Level Loop is done going depth-first on each
  #   parallel branch
  if (currentDigit == (maxLen - 1)):
    # print("EXITTING recursion after processing MAX DIGIT INDEX!")
    return (isWordFoundAtDeeperLevel or isWordFoundAtLevel)
  else:
    # ATTN:  CHAIN result for flagging word found ACROSS recursion levels; 
    #        and within-LEVEL letter branches
    # BUT don't use this as a condition to block deeper branch-exploration recursion 
    # which would do a ROLLBACK of BUILD-RESULTS UP BRANCH from LEAF to ROOT
    # when DEEPEST-LEAF result is EAGERLY-DFS found to be FALSE CONDITION
    # eg as you'd code up for FIND VALID PATH DFS traversal!
    # print("DEFAULT exit recursion after processing ANY LEVEL")
    return (isWordFoundAtDeeperLevel or isWordFoundAtLevel)
    
# ********** TEST DRIVER *************

# assume static members of class or known non-stack data!
digitToLetters = { "2":"ABC", "8":"TUV", "4":"GHI" }
realWordsAll = {"A", "AT", "BAT", "CAT", "ACT", "BATH"}

# TEST CASES

# one-digit, valid word
phoneNum10 = "2"
# returns True, mutates to ['A'] as real word found

# one-digit, invalid word
# override realWordsAll
realWords11 = {"BOGUS"}
phoneNum11 = "2"
# returns False, mutates to [] as no real word found

# two-digit, valid word
phoneNum20 = "28" 

# three-digit, valid words, one repeated digit
phoneNum30 = "228"

# four-digit, valid words
phoneNum41 = "2284"

# five-digit, invalid words
phoneNum42 = "2284"
# realWords = realWords11

# TEST DRIVER for specific CASE
phoneNum = phoneNum42
# realWords = realWords11
realWords = realWordsAll

# generic driver code for all cases
# ATTN:  buildingWord must be MUTABLE!
buildingWord = []
try:
  atLeastOneValid = findWords(phoneNum, 0, buildingWord)
  print("Is Found at least one valid word?  {}".format(atLeastOneValid))
except ValueError as vErr:
  print(vErr)
except Exception as ex:
  raise(ex)