# DCP22 - TheQuickBrownFox

Sep 14th, 2020
762
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. This problem was asked by Microsoft.
3. Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list.
4. If there is more than one possible reconstruction, return any of them. If there is no possible reconstruction, then return null.
5. For example, given the set of words 'quick', 'brown', 'the', 'fox', and the string "thequickbrownfox", you should return ['the', 'quick', 'brown', 'fox'].
6. Given the set of words 'bed', 'bath', 'bedbath', 'and', 'beyond', and the string "bedbathandbeyond", return either
7. ['bed', 'bath', 'and', 'beyond] or ['bedbath', 'and', 'beyond'].
8. '''
9.
10. def isPrefix(word, message):
11.     n = len(word)
12.     if n > len(message):
13.         return "ERROR"
14.     for i in range(n):
15.         if word[i] != message[i]:
16.             return False
17.     return True
18.
19.
20. def solve(words, message):
21.     messageCopy = message
22.     # First, I will check the lengths
23.     sum = 0
24.     for word in words:
25.         sum += len(word)
26.     if len(message) != sum:
27.         return "The lengths of words list and the given message are not compatible."
28.
29.     # Now, I will start to "cut" the message
30.     returnedWords = list()
31.     while len(messageCopy) > 0:
32.         isThereAPrefixInMessageCopy = False
33.         prefix = ""
34.         for word in words:
35.             if isPrefix(word, messageCopy):
36.                 isThereAPrefixInMessageCopy = True
37.                 prefix = word
38.                 break
39.         # Now, I know if there is a prefix and what it is
40.         if isThereAPrefixInMessageCopy == False:
41.             # print("There is no prefix found.")
42.             return None
43.         else:
44.             # I have to do 3 things: 1 ---> add the prefix in returned list
45.             #                        2 ---> remove the word-prefix from "words" list
46.             #                        3 ---> cut the messageCopy
47.             returnedWords.append(prefix)
48.             words.remove(prefix)
49.             n = len(prefix)
50.             messageCopy = messageCopy[n:]
51.     return returnedWords
52.
53.
54.
55.
56. # MAIN FUNCTION
57. print()
58. print("******** Case 1 ********")
59. words1 = ['quick', 'the', 'fox', 'brown']
60. message1 = 'thequickbrownfox'
61. print("words = " + str(words1) + ", message = " + str(message1) + " ----> " + str(solve(words1, message1)))
62. print("******** Case 2 ********")
63. words1 = ['quick', 'the', 'box', 'brown']
64. message1 = 'thequickbrownfox'
65. print("words = " + str(words1) + ", message = " + str(message1) + " ----> " + str(solve(words1, message1)))
66. print("******** Case 3 ********")
67. words1 = ['quick', 'the', 'fox', 'red']
68. message1 = 'thequickbrownfox'
69. print("words = " + str(words1) + ", message = " + str(message1) + " ----> " + str(solve(words1, message1)))
RAW Paste Data