Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
"""
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!")
isWordFoundAtDeeperLevel = True
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.