makispaiktis

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