DCP22 - TheQuickBrownFox

'''
This problem was asked by Microsoft.
Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list.
If there is more than one possible reconstruction, return any of them. If there is no possible reconstruction, then return null.
For example, given the set of words 'quick', 'brown', 'the', 'fox', and the string "thequickbrownfox", you should return ['the', 'quick', 'brown', 'fox'].
Given the set of words 'bed', 'bath', 'bedbath', 'and', 'beyond', and the string "bedbathandbeyond", return either
['bed', 'bath', 'and', 'beyond] or ['bedbath', 'and', 'beyond'].
'''

def isPrefix(word, message):
    n = len(word)
    if n > len(message):
        return "ERROR"
    for i in range(n):
        if word[i] != message[i]:
            return False
    return True


def solve(words, message):
    messageCopy = message
    # First, I will check the lengths
    sum = 0
    for word in words:
        sum += len(word)
    if len(message) != sum:
        return "The lengths of words list and the given message are not compatible."

    # Now, I will start to "cut" the message
    returnedWords = list()
    while len(messageCopy) > 0:
        isThereAPrefixInMessageCopy = False
        prefix = ""
        for word in words:
            if isPrefix(word, messageCopy):
                isThereAPrefixInMessageCopy = True
                prefix = word
                break
        # Now, I know if there is a prefix and what it is
        if isThereAPrefixInMessageCopy == False:
            # print("There is no prefix found.")
            return None
        else:
            # I have to do 3 things: 1 ---> add the prefix in returned list
            #                        2 ---> remove the word-prefix from "words" list
            #                        3 ---> cut the messageCopy
            returnedWords.append(prefix)
            words.remove(prefix)
            n = len(prefix)
            messageCopy = messageCopy[n:]
    return returnedWords




# MAIN FUNCTION
print()
print("******** Case 1 ********")
words1 = ['quick', 'the', 'fox', 'brown']
message1 = 'thequickbrownfox'
print("words = " + str(words1) + ", message = " + str(message1) + " ----> " + str(solve(words1, message1)))
print("******** Case 2 ********")
words1 = ['quick', 'the', 'box', 'brown']
message1 = 'thequickbrownfox'
print("words = " + str(words1) + ", message = " + str(message1) + " ----> " + str(solve(words1, message1)))
print("******** Case 3 ********")
words1 = ['quick', 'the', 'fox', 'red']
message1 = 'thequickbrownfox'
print("words = " + str(words1) + ", message = " + str(message1) + " ----> " + str(solve(words1, message1)))