{"id":832,"date":"2021-03-05T11:46:40","date_gmt":"2021-03-05T03:46:40","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=832"},"modified":"2021-03-05T14:18:55","modified_gmt":"2021-03-05T06:18:55","slug":"leetcode-648","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/03\/05\/leetcode-648\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 648 – Replace Words"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t

\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4>

In English, we have a concept called <\/span>root<\/span><\/strong><\/span>, which can be followed by some other word to form another longer word – let’s call this word <\/span>successor<\/span><\/strong><\/span>. For example, when the <\/span>root<\/span><\/strong><\/span> \"an\"<\/code><\/span> is followed by the <\/span>successor<\/span><\/strong><\/span> word <\/span>\"other\"<\/code><\/span>, we can form a new word <\/span>\"another\"<\/code><\/span>.<\/span><\/p>

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

Return <\/span>the <\/span>sentence<\/code><\/span><\/em><\/span> after the replacement.<\/span><\/p>

\u00a0<\/p>

Example 1:<\/span><\/strong><\/span><\/p>

Input: dictionary = [\"cat\",\"bat\",\"rat\"], sentence = \"the cattle was rattled by the battery\"<\/span>
Output: \"the cat was rat by the bat\"<\/span><\/pre>
Example 2:<\/span><\/strong><\/span><\/p>
Input: dictionary = [\"a\",\"b\",\"c\"], sentence = \"aadsfasf absbs bbab cadsfafs\"<\/span>
Output: \"a a b c\"<\/span><\/pre>
Example 3:<\/span><\/strong><\/span><\/p>
Input: dictionary = [\"a\", \"aa\", \"aaa\", \"aaaa\"], sentence = \"a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa\"<\/span>
Output: \"a a a a a a a a bbb baba a\"<\/span><\/pre>
Example 4:<\/span><\/strong><\/span><\/p>
Input: dictionary = [\"catt\",\"cat\",\"bat\",\"rat\"], sentence = \"the cattle was rattled by the battery\"<\/span>
Output: \"the cat was rat by the bat\"<\/span><\/pre>
Example 5:<\/span><\/strong><\/span><\/p>
Input: dictionary = [\"ac\",\"ab\"], sentence = \"it is abnormal that this solution is accepted\"<\/span>
Output: \"it is ab that this solution is ac\"<\/span><\/pre>
\u00a0<\/p>
Constraints:<\/span><\/strong><\/span><\/p>
  • 1 <= dictionary.length <= 1000<\/code><\/span><\/p><\/li>
  • 1 <= dictionary[i].length <= 100<\/code><\/span><\/p><\/li>
  • dictionary[i]<\/code><\/span> consists of only lower-case letters.<\/span><\/p><\/li>
  • 1 <= sentence.length <= 10^6<\/code><\/span><\/p><\/li>
  • sentence<\/code><\/span> consists of only lower-case letters and spaces.<\/span><\/p><\/li>
  • The number of words in <\/span>sentence<\/code><\/span> is in the range <\/span>[1, 1000]<\/code><\/span><\/p><\/li>
  • The length of each word in <\/span>sentence<\/code><\/span> is in the range <\/span>[1, 1000]<\/code><\/span><\/p><\/li>
  • Each two consecutive words in <\/span>sentence<\/code><\/span> will be separated by exactly one space.<\/span><\/p><\/li>
  • sentence<\/code><\/span> does not have leading or trailing spaces.<\/span><\/p><\/li><\/ul>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    \u4e00\u5237\u984c\u89e3\uff08Trie\uff09\uff1a<\/strong><\/span><\/h4>
    \u00a0 \u00a0 \u00a0 \u00a0 \u9019\u984c\u7d66\u4e86\u6211\u5011\u4e00\u500b\u300c\u5b57\u6839\u300d\u5217\u8868\uff0c\u9084\u6709\u4e00\u500b\u53e5\u5b50\u5b57\u7b26\u4e32\uff0c\u8981\u6211\u5011\u5728\u9019\u500b\u53e5\u5b50\u4e2d\u627e\u51fa\u6240\u6709\u901a\u904e\u300c\u5b57\u6839 + \u4e00\u4e9b\u5b57\u6bcd\u300d\u7d44\u6210\u7684\u55ae\u8a5e\uff0c\u7136\u5f8c\u5c07\u9019\u4e9b\u55ae\u8a5e\u7528\u5b57\u6839\u53d6\u4ee3\u3002\u5c0d\u6b64\uff0c\u6211\u5011\u9700\u8981\u5169\u6b65\u5de5\u5e8f\uff1a<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u7b2c\u4e00\u6b65\uff0c\u5c07\u5b57\u6839\u88e1\u7684\u5b57\u7b26\u4e32\u653e\u5230\u4e00\u500b\u5b57\u9996\u6a39\u4e2d\uff0c\u69cb\u9020\u4e00\u500b\u5305\u542b\u4e86\u6240\u6709\u6307\u5b9a\u5b57\u6839\u7684\u5b57\u9996\u6a39\u3002<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u7b2c\u4e8c\u6b65\uff0c\u628a\u5b57\u9996\u6a39\u69cb\u5efa\u5b8c\u6210\u5f8c\uff0c\u518d\u5c0d\u53e5\u5b50\u4e2d\u7684\u6bcf\u500b\u55ae\u8a5e\u9032\u884c\u904d\u6b77\uff0c\u6aa2\u67e5\u9019\u4e9b\u55ae\u8a5e\u662f\u5426\u5305\u542b\u5b57\u9996\u6a39\u4e2d\u6240\u8a18\u9304\u7684\u5b57\u7b26\u3002\u5982\u679c\u5305\u542b\uff0c\u5247\u4ee3\u8868\u55ae\u8a5e\u662f\u7531\u5b57\u6839\u6216\u5b57\u6839+\u4e00\u4e9b\u5b57\u6bcd\u6240\u7d44\u6210\u7684\uff0c\u90a3\u5c31\u53ef\u4ee5\u7528\u5b57\u6839\u5c07\u5176\u53d6\u4ee3\uff0c\u5982\u679c\u4e0d\u5305\u542b\uff0c\u90a3\u5c31\u76f4\u63a5\u9032\u5165\u4e0b\u4e00\u500b\u55ae\u8a5e\u7684\u6aa2\u67e5\u4e2d\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    public<\/span> class<\/span> Solution<\/span> {<\/span>
     \u00a0 \u00a0public<\/span> string<\/span> ReplaceWords<\/span>(IList<\/span><<\/span>string<\/span>><\/span> dictionary<\/span>, string<\/span> sentence<\/span>) {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/Pass 1: \u6839\u64daroot\u69cb\u5efa\u5b57\u9996\u6a39<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0TrieNode<\/span> rootNode<\/span> =<\/span> new<\/span> TrieNode<\/span>();<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0foreach<\/span>(string<\/span> root<\/span> in<\/span> dictionary<\/span>)<\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0TrieNode<\/span> curr<\/span> =<\/span> rootNode<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0foreach<\/span>(char<\/span> c<\/span> in<\/span> root<\/span>.ToCharArray<\/span>())<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(curr<\/span>.children<\/span>[c<\/span> -<\/span> 'a'<\/span>] ==<\/span> null<\/span>) { curr<\/span>.children<\/span>[c<\/span> -<\/span> 'a'<\/span>] =<\/span> new<\/span> TrieNode<\/span>(); }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0curr<\/span> =<\/span> curr<\/span>.children<\/span>[c<\/span> -<\/span> 'a'<\/span>];<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0curr<\/span>.word<\/span> =<\/span> root<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0StringBuilder<\/span> sb<\/span> =<\/span> new<\/span> StringBuilder<\/span>();<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0string<\/span>[] words<\/span> =<\/span> sentence<\/span>.Split<\/span>(' '<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/Pass 2: \u904d\u6b77\u53e5\u5b50\u4e2d\u7684\u6240\u6709\u5b57\u7b26\u4e32\uff0c\u6aa2\u67e5\u662f\u5426\u5305\u542broot<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0foreach<\/span>(string<\/span> word<\/span> in<\/span> words<\/span>)<\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(sb<\/span>.Length<\/span> ><\/span> 0<\/span>) { sb<\/span>.Append<\/span>(\" \"<\/span>); } \/\/\u5982\u679c\u52a0\u904e\u4e86\u4e00\u500b\u5143\u7d20\uff0c\u6bcf\u6b21\u904d\u6b77\u524d\u5148\u52a0\u4e00\u500b\u7a7a\u683c<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0TrieNode<\/span> curr<\/span> =<\/span> rootNode<\/span>; \/\/\u904d\u6b77\u5b57\u9996\u6a39<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/\u904d\u6b77\u6bcf\u500b\u5b57\u7b26\u4e32\u4e2d\u7684\u6240\u6709\u5b57\u7b26<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0foreach<\/span>(char<\/span> c<\/span> in<\/span> word<\/span>.ToCharArray<\/span>())<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/\u5b57\u7b26\u8207root\u4e4b\u9593\u6709\u51fa\u5165 || \u904d\u6b77\u5230root\u7684\u5e95\u90e8\uff08curr.word != null\uff09<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(curr<\/span>.children<\/span>[c<\/span> -<\/span> 'a'<\/span>] ==<\/span> null<\/span> ||<\/span> curr<\/span>.word<\/span> !=<\/span> null<\/span>) { break<\/span>; }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/\u79fb\u52d5\u5230\u4e0b\u500b\u7bc0\u9ede<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0curr<\/span> =<\/span> curr<\/span>.children<\/span>[c<\/span> -<\/span> 'a'<\/span>];<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/\u5982\u679c\u5b57\u7b26\u4e32\u8207\u4e0d\u5305\u542broot\uff0c\u76f4\u63a5\u8fd4\u56de\u539f\u5b57\u7b26\uff0c\u5426\u5247\u5c31\u4f7f\u7528root\u53d6\u4ee3\u539f\u5b57\u7b26<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0sb<\/span>.Append<\/span>(curr<\/span>.word<\/span> ==<\/span> null<\/span> ?<\/span> word<\/span> : curr<\/span>.word<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0return<\/span> sb<\/span>.ToString<\/span>();<\/span>
     \u00a0  }<\/span>
    }<\/span>

    public<\/span> class<\/span> TrieNode<\/span><\/span>
    {<\/span>
     \u00a0 \u00a0public<\/span> TrieNode<\/span>[] children<\/span> =<\/span> new<\/span> TrieNode<\/span>[26<\/span>];<\/span>
     \u00a0 \u00a0public<\/span> string<\/span> word<\/span> =<\/span> null<\/span>;<\/span>
    }<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
    \u984c\u76ee\u63cf\u8ff0\uff1a In English, we have a concept called root, which  …<\/p>\n
      [LeetCode\u5237\u984c\u7b46\u8a18] 648 – Replace Words<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":570,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,16],"tags":[],"class_list":["post-832","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming-notes","category-leetcodes"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/lonelinerd.com\/wp-content\/uploads\/2021\/02\/FeatureCover_LeetCoding.png","_links":{"self":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/832","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/comments?post=832"}],"version-history":[{"count":8,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/832\/revisions"}],"predecessor-version":[{"id":842,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/832\/revisions\/842"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media\/570"}],"wp:attachment":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media?parent=832"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=832"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=832"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}