In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.




Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.



You need to output the sentence after the replacement.



Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"




Note:

The input will only have lower-case letters.
 1 
 1 
 1 
 1

Difficulty: interview

Starter code:

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        

Solutions:
class Solution:
     def replaceWords(self, dt, sentence):
         """
         :type dict: List[str]
         :type sentence: str
         :rtype: str
         """
         trie = {}
         for w in dt:
             t = trie
             for c in w:
                 if c not in t:  t[c] = {}
                 t = t[c]
             t['#'] = w
             
         # result = []
         
 #         for word in sentence.split():
 #             result.append(self.replace(word, trie))
         
 #         return " ".joinresult 
     
 #     OR
         return  " ".join([ self.replace(i, trie) for i in sentence.split() ])
     
         
         
     
     def replace( self, word, trie ):
         cur = trie
         for letter in word:
             if letter not in cur: break
             cur = cur[letter]
             if "#" in cur:
                 return cur['#']
         return word
         
         
         setenceAsList = sentence.split(" ")
         for i in range(len(setenceAsList)):
             for j in dt:
                 if setenceAsList[i].startswith(j):
                     setenceAsList[i] = j
         return " ".join(setenceAsList)
     
         arrs = sentence.split()
         for i in range(len(arrs)):
             w = arrs[i]
             for j in range(len(arrs[i])):
                 cur = w[:j]
                 if cur in dt:
                     arrs[i] = cur
                     break
         return ' '.join(arrs)


class Solution:
     
     def replaceWords(self, roots, sentence):
         
         # create a trie with roots words
 
         trie = {}
         for w in roots:
             t = trie
             for c in w:
                 if c not in t:  t[c] = {}
                 t = t[c]
             t['#'] = True
         # print(trie)
 #        result = []
         return  " ".join([ self.replace(i, trie) for i in sentence.split() ])
     
         
         
     
     def replace( self, word, trie ):
         cur = trie
         i=0
         for letter in word:
             if letter not in cur: break
             cur = cur[letter]
             i+=1
             if "#" in cur:
                 return word[:i]
         return word


class Solution:
     def replaceWords(self, dict, sentence):
         """
         :type dict: List[str]
         :type sentence: str
         :rtype: str
         """
         #O(NS) time; O(N) space
         #constructing Trie using nested dictionary
         
         trie = {}
         
         #populate the Trie
         for root in dict:
             node = trie           
             for letter in root:
                 if letter not in node:
                     node[letter] = {}
                 node = node[letter]
             node["#"] = root 
             
         #traverse the trie
         words = []
         for word in sentence.split():
             node = trie
             for letter in word:
                 if letter not in node or "#" in node:
                     break
                 node = node[letter]
             if "#" in node:
                 words.append(node["#"])
             else:
                 words.append(word)
         return str.join(" ",words)                    
                 
   
 
                     


class Solution:
     def replaceWords(self, dict, sentence):
         trie_tree = {'root': {}}
         for word in dict:
             parent = trie_tree['root']
             for c in word + '#':
                 parent.setdefault(c, {})
                 parent = parent[c]
         sentence, res = sentence.split(), []
         for word in sentence:
             parent = trie_tree['root']
             for i, c in enumerate(word + '*'):
                 if c not in parent:
                     res.append(word)
                     break
                 parent = parent[c]
                 if '#' in parent:
                     res.append(word[:i + 1])
                     break
         return ' '.join(res)

class Solution:
     def replaceWords(self, dict, sentence):
         """
         :type dict: List[str]
         :type sentence: str
         :rtype: str
         """
         sentence = sentence + ' '
         dic = {}
         for i in dict:
             if i[0] not in list(dic.keys()):
                 dic[i[0]] = [i]
             else:
                 dic[i[0]].append(i)
         res = ''
         while len(sentence) > 0:
             word = sentence[:sentence.index(' ')]
             tmp = ''
             if word[0] in list(dic.keys()):
                 for refer in dic[word[0]]:
                     if len(refer) < len(word):
                         if word[:len(refer)] == refer:
                             if tmp == '':
                                 tmp = refer
                             else:
                                 if len(tmp) > len(refer):
                                     tmp = refer
             if tmp != '':
                 res += tmp+' '
             else:
                 res += word+' '                     
             sentence = sentence[sentence.index(' ')+1:]
         res = res[:-1]
         return res