{"id":4267,"date":"2018-11-08T20:42:30","date_gmt":"2018-11-09T04:42:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4267"},"modified":"2018-11-08T20:43:32","modified_gmt":"2018-11-09T04:43:32","slug":"leetcode-648-replace-words","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-648-replace-words\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 648. Replace Words"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

https:\/\/leetcode.com\/problems\/replace-words\/description\/<\/a><\/p>\n

In English, we have a concept called\u00a0root<\/code>, which can be followed by some other words to form another longer word – let’s call this word\u00a0successor<\/code>. For example, the root\u00a0an<\/code>, followed by\u00a0other<\/code>, which can form another word\u00a0another<\/code>.<\/p>\n

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the\u00a0successor<\/code>\u00a0in the sentence with the\u00a0root<\/code>\u00a0forming it. If a\u00a0successor<\/code>\u00a0has many\u00a0roots<\/code>\u00a0can form it, replace it with the root with the shortest length.<\/p>\n

You need to output the sentence after the replacement.<\/p>\n

Example 1:<\/b><\/p>\n

Input:<\/b> dict = [\"cat\", \"bat\", \"rat\"]\r\nsentence = \"the cattle was rattled by the battery\"\r\nOutput:<\/b> \"the cat was rat by the bat\"\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. The input will only have lower-case letters.<\/li>\n
  2. 1 <= dict words number <= 1000<\/li>\n
  3. 1 <= sentence words number <= 1000<\/li>\n
  4. 1 <= root length <= 100<\/li>\n
  5. 1 <= sentence words length <= 1000<\/li>\n<\/ol>\n
    Solution 1: HashTable<\/strong><\/h1>\n
    Time complexity: O(sum(w^2))<\/p>\n
    Space complexity: O(sum(l))<\/p>\n
    \/\/ Author: Huahua, Running time: 84 ms\r\nclass Solution {\r\npublic:\r\n  string replaceWords(vector<string>& dict, string sentence) {\r\n    unordered_set<string> d(begin(dict), end(dict));\r\n    sentence.push_back(' ');\r\n    string output;\r\n    string word;\r\n    bool found = false;\r\n    for (char c : sentence) {\r\n      if (c == ' ') {\r\n        if (!output.empty()) output += ' ';\r\n        output += word;\r\n        word = \"\";\r\n        found = false;\r\n        continue;\r\n      }\r\n      if (found) continue;\r\n      word += c;\r\n      if (d.count(word)) {\r\n        found = true;\r\n      }\r\n    }\r\n    return output;\r\n  }\r\n};<\/pre>\n
    Solution2: Trie<\/strong><\/h2>\n
    Time complexity: O(sum(l) + n)<\/p>\n
    Space complexity: O(sum(l) * 26)<\/p>\n
    \/\/ Author: Huahua, running time: 48 ms\r\nclass TrieNode {\r\npublic:\r\n  TrieNode(): children(26), is_word(false) {}\r\n  ~TrieNode() {\r\n    for (int i = 0; i < 26; ++i)\r\n      if (children[i]) {\r\n        delete children[i];\r\n        children[i] = nullptr;\r\n      }\r\n  }\r\n  vector<TrieNode*> children;\r\n  bool is_word;\r\n};\r\nclass Solution {\r\npublic:\r\n  string replaceWords(vector<string>& dict, string sentence) {    \r\n    TrieNode root;\r\n    for (const string& word : dict) {\r\n      TrieNode* cur = &root;\r\n      for (char c : word) {        \r\n        if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();\r\n        cur = cur->children[c - 'a'];\r\n      }\r\n      cur->is_word = true;\r\n    }\r\n    \r\n    string ans;\r\n    stringstream ss(sentence);\r\n    string word;\r\n    while (ss >> word) {      \r\n      TrieNode* cur = &root;\r\n      bool found = false;\r\n      int len = 0;\r\n      for (char c : word) {        \r\n        cur = cur->children[c - 'a'];        \r\n        if (!cur) break;\r\n        ++len;\r\n        if (cur->is_word) {\r\n          found = true;\r\n          break;\r\n        }\r\n      }      \r\n      if (!ans.empty()) ans += ' ';      \r\n      ans += found ? word.substr(0, len) : word;\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
     <\/p>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem https:\/\/leetcode.com\/problems\/replace-words\/description\/ In English, we have a concept called\u00a0root, which can be followed by some other words to form another longer word – let’s call…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70,47],"tags":[82,177,97,430,4,96],"class_list":["post-4267","post","type-post","status-publish","format-standard","hentry","category-hashtable","category-string","tag-hashtable","tag-medium","tag-prefix","tag-replace","tag-string","tag-trie","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4267"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4267\/revisions"}],"predecessor-version":[{"id":4269,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4267\/revisions\/4269"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}