leetcode：648. Word replacement [dictionary tree board + find the shortest matching prefix among several prefixes]

analysis

To a Trie Record dictionary tree
Then traverse word by word , use cur Go to the current layer
If you traverse to a c, Not in the cur in , Set up cur[c] It's empty , cur = cur[c]
At the end, let's say # It means the ending
Then traverse sentence Every word in , If you traverse to # Description matches a prefix , Prefix replacement
If you find out that c be not in cur in , It means that there is no match , direct break

ac code

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        #  Dictionary tree board 
        trie = {
    }
        for word in dictionary:
            cur = trie
            for c in word:
                #  New branch 
                if c not in cur:
                    cur[c] = {
    }
                cur = cur[c]
            #  End mark 
            cur['#'] = {
    }
        
        words = sentence.split()
        for i in range(len(words)):
            #  stay trie Find the shortest prefix 
            cur = trie
            for j, c in enumerate(words[i]):
                #  Match to the first prefix 
                if '#' in cur:
                    words[i] = words[i][:j]
                    break
                #  Matching failure 
                if c not in cur:
                    break
                #  Continue matching 
                cur = cur[c]
        #print(words)
        return ' '.join(words)

summary

Dictionary tree board
You can find the shortest matching prefix among several prefixes