Adam
BAN USERI solved this in Python using a Trie. When we're done adding a word, we go through all of the nodes used to store the word and increment the frequency of the appropriate child letter. When we want to find out which character to choose next, we navigate down the Trie using the prefix provided, then we simply find which child character has the highest frequency. That last part could be improved by using a max heap, or it could also be modified to return a list of characters in the case that there's a tie for highest frequency.
def getIndex(alphabetLetter) :
return ord(alphabetLetter.lower()) - ord('a')
def getChar(index0To25):
return chr(index0To25 + ord('a'))
class Trie(object):
def __init__(self, parent):
self.parent = parent
self.isWord = False
self.children = [None for i in range(26)]
self.frequencies = [0 for i in range(26)]
# Go through the parents and update frequencies.
def addedDescendantWord(self, originalWord, depth) :
char = originalWord[depth]
charIndex = getIndex(char)
self.frequencies[charIndex] += 1
if self.parent is not None :
self.parent.addedDescendantWord(originalWord, depth - 1)
def addWord(self, word, originalWord=None) :
if originalWord is None : originalWord = word
firstChar = word[0]
childIndex = getIndex(firstChar)
if self.children[childIndex] is None :
self.children[childIndex] = Trie(self)
child = self.children[childIndex]
if len(word) is 1 :
if not child.isWord :
# A new word was added, so alert all parents that they have a
# new descendant.
child.isWord = True
self.addedDescendantWord(originalWord, len(originalWord) - 1)
return
self.children[childIndex].addWord(word[1:], originalWord)
def getNextChar(self, prefix) :
if len(prefix) is 0 :
# Select the highest frequency and return the index
maxIndex = 0
for i in range(26) :
if self.frequencies[i] > self.frequencies[maxIndex] :
maxIndex = i
if self.frequencies[maxIndex] is 0 :
return "[not applicable]"
return getChar(maxIndex)
firstChar = prefix[0]
childIndex = getIndex(firstChar)
child = self.children[childIndex]
if child is None:
return "[not applicable]"
return child.getNextChar(prefix[1:])
def testGetNext(trie, prefix):
choice = trie.getNextChar(prefix)
print "Best choice after \"%s\" is \"%s\"" % (prefix, choice)
def main() :
trie = Trie(None)
# Add some words
map(trie.addWord, ["ac", "ab", "abc", "abc", "abcd", "bcd", "cba"])
# Test some cases
[testGetNext(trie, test) for test in ["a", "ab", "abc", "abcd", "abcde"]]
if __name__ == '__main__':
main()
Output:
Best choice after "a" is "b"
Best choice after "ab" is "c"
Best choice after "abc" is "d"
Best choice after "abcd" is "[not applicable]"
Best choice after "abcde" is "[not applicable]"
The question asks to "output the amount of all possible strings", so I haven't quite answered that below; rather, I've outputted all possible strings. I believe this solution is essentially what HoneyBall was describing.
Output:
- Adam November 25, 2013