[LeetCode刷題筆記] 648 – Replace Words

題目描述:

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"

Example 3:

Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"

Example 4:

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

Example 5:

Input: dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
Output: "it is ab that this solution is ac"

 

Constraints:

  • 1 <= dictionary.length <= 1000

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

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

  • 1 <= sentence.length <= 10^6

  • 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]

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

  • sentence does not have leading or trailing spaces.

一刷題解(Trie):

        這題給了我們一個「字根」列表,還有一個句子字符串,要我們在這個句子中找出所有通過「字根 + 一些字母」組成的單詞,然後將這些單詞用字根取代。對此,我們需要兩步工序:

        第一步,將字根裡的字符串放到一個字首樹中,構造一個包含了所有指定字根的字首樹。

        第二步,把字首樹構建完成後,再對句子中的每個單詞進行遍歷,檢查這些單詞是否包含字首樹中所記錄的字符。如果包含,則代表單詞是由字根或字根+一些字母所組成的,那就可以用字根將其取代,如果不包含,那就直接進入下一個單詞的檢查中。

public class Solution {
   public string ReplaceWords(IList<string> dictionary, string sentence) {
       //Pass 1: 根據root構建字首樹
       TrieNode rootNode = new TrieNode();
       foreach(string root in dictionary)
      {
           TrieNode curr = rootNode;
           foreach(char c in root.ToCharArray())
          {
               if(curr.children[c - 'a'] == null) { curr.children[c - 'a'] = new TrieNode(); }
               curr = curr.children[c - 'a'];
          }
           curr.word = root;
      }
       
       StringBuilder sb = new StringBuilder();
       string[] words = sentence.Split(' ');
       
       //Pass 2: 遍歷句子中的所有字符串,檢查是否包含root
       foreach(string word in words)
      {
           if(sb.Length > 0) { sb.Append(" "); } //如果加過了一個元素,每次遍歷前先加一個空格
           TrieNode curr = rootNode; //遍歷字首樹
           //遍歷每個字符串中的所有字符
           foreach(char c in word.ToCharArray())
          {
               //字符與root之間有出入 || 遍歷到root的底部(curr.word != null)
               if(curr.children[c - 'a'] == null || curr.word != null) { break; }
               //移動到下個節點
               curr = curr.children[c - 'a'];
          }
           //如果字符串與不包含root,直接返回原字符,否則就使用root取代原字符
           sb.Append(curr.word == null ? word : curr.word);
      }
       
       return sb.ToString();
  }
}

public class TrieNode
{
   public TrieNode[] children = new TrieNode[26];
   public string word = null;
}