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

Given a?dictionary?consisting of many?roots?and a?sentence?consisting of words separated by spaces, replace all the?successors?in the sentence with the?root?forming it. If a?successor?can be replaced by more than one?root, replace it with the?root?that has?the shortest length.

Return?the?sentence?after the replacement.

?

Example 1:

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

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"Output: "a a b c"

?

Constraints:

• 1 <= dictionary.length <= 1000

• 1 <= dictionary[i].length <= 100

• dictionary[i]?consists of only lower-case letters.

• 1 <= sentence.length <= 106

• sentence?consists of only lower-case letters and spaces.

• The number of words in?sentence?is in the range?[1, 1000]

• The length of each word in?sentence?is in the range?[1, 1000]

• Every two consecutive words in?sentence?will be separated by exactly one space.

• sentence?does not have leading or trailing spaces.

這道題大部分人用的是字典樹(shù)，我沒(méi)有用過(guò)這種數(shù)據(jù)結(jié)構(gòu)，以后可以學(xué)習(xí)一下，我用的是string.stratwith的函數(shù)，也是可以確認(rèn)的；

正則表達(dá)式將字符串按照空格就行分列，這里面要轉(zhuǎn)義字符也就是\\s才行。

下面是代碼：

Runtime:?198 ms, faster than?38.91%?of?Java?online submissions for?Replace Words.

Memory Usage:?55.1 MB, less than?56.08%?of?Java?online submissions for?Replace Words.