LeetCode- Replace Words Solution

题目:

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.

 

使用Hash实现


  将root存储到使用Hash表, 将要处理的句子拆分后遍历所有单词,通过hash进行判断

    • 时间复杂度O(n²), 其中n为每个单词匹配到root的长度
    • 空间复杂度O(n), rootset存放root
  • java实现:
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
// 定义一个hashset,存放root
Set<String> rootset = new HashSet<String>();
for(String root: dictionary) {
rootset.add(root);
}
// 将每个单词从sentence中分割出来,<br> // 存放到一个StringBuilder中
StringBuilder ans = new StringBuilder();
for (String word: sentence.split("\\s+") ) {
String prefix="";
// 判断单词前缀是否在hashset中。
for (int i=1; i<=word.length(); i++){
prefix = word.substring( 0, i);
if (rootset.contains(prefix)) {
break;
}
}
if (ans.length() > 0 ) {
ans.append(" ");
}
ans.append(prefix);
}
// 返回
return ans.toString();
}
}
class Solution { public String replaceWords(List<String> dictionary, String sentence) { // 定义一个hashset,存放root Set<String> rootset = new HashSet<String>(); for(String root: dictionary) { rootset.add(root); } // 将每个单词从sentence中分割出来,<br> // 存放到一个StringBuilder中 StringBuilder ans = new StringBuilder(); for (String word: sentence.split("\\s+") ) { String prefix=""; // 判断单词前缀是否在hashset中。 for (int i=1; i<=word.length(); i++){ prefix = word.substring( 0, i); if (rootset.contains(prefix)) { break; } } if (ans.length() > 0 ) { ans.append(" "); } ans.append(prefix); } // 返回 return ans.toString(); } }
class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        // 定义一个hashset,存放root
        Set<String> rootset = new HashSet<String>();
        for(String root: dictionary) {
            rootset.add(root);
        }
        
        // 将每个单词从sentence中分割出来,
// 存放到一个StringBuilder中 StringBuilder ans = new StringBuilder(); for (String word: sentence.split("\\s+") ) { String prefix=""; // 判断单词前缀是否在hashset中。 for (int i=1; i<=word.length(); i++){ prefix = word.substring( 0, i); if (rootset.contains(prefix)) { break; } } if (ans.length() > 0 ) { ans.append(" "); } ans.append(prefix); } // 返回 return ans.toString(); } }
  • python实现:
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
rootset = set(dictionary)
def replace(word):
for i in range(1, len(word)):
if word[:i] in rootset:
return word[:i]
return word
return " ".join(map(replace, sentence.split()))
class Solution: def replaceWords(self, dictionary: List[str], sentence: str) -> str: rootset = set(dictionary) def replace(word): for i in range(1, len(word)): if word[:i] in rootset: return word[:i] return word return " ".join(map(replace, sentence.split()))
class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        rootset = set(dictionary)
        def replace(word):   
            for i in range(1, len(word)):
                if word[:i] in rootset:
                    return word[:i]
            return word

        return " ".join(map(replace, sentence.split()))
        

 

使用Trie树实现


    •  时间复杂度O(n),   n 为所有字符串长度和, 搜索所有字符串
    • 空间复杂度O(n),n 为 Trie树空间
  • java实现
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
class TrieNode {
TrieNode[] children;
String word;
TrieNode(){
children = new TrieNode[26];
/*默认初始化null
for (int i=0; i<26; i++){
children[i] = null;
}
*/
}
}
class Solution{
public String replaceWords(List<String> dictionary, String sentence) {
// 将字典数据存放数Trie树中
TrieNode trie = new TrieNode();
for (String root: dictionary) {
//从头开始遍历
TrieNode cur =trie;
for (char letter: root.toCharArray()){
if (cur.children[letter - 'a'] == null){
cur.children[letter - 'a'] = new TrieNode();
}
cur = cur.children[letter - 'a'];
}
cur.word = root;
}
// 将句子按照空格分割程单词依次判断是否在Trie树中,
// 不存在使用原有单词, 完成新句子拼接
StringBuilder ans = new StringBuilder();
for (String word: sentence.split("\\s+")){
if (ans.length() > 0){
ans.append(" " );
}
TrieNode cur = trie;
for (char letter:word.toCharArray()){
if (cur.children[letter - 'a'] == null ||\<br> cur.word != null){
break;
}
cur = cur.children[letter - 'a'];
}
ans.append(cur.word!=null?cur.word:word);
}
return ans.toString();
}
}
class TrieNode { TrieNode[] children; String word; TrieNode(){ children = new TrieNode[26]; /*默认初始化null for (int i=0; i<26; i++){ children[i] = null; } */ } } class Solution{ public String replaceWords(List<String> dictionary, String sentence) { // 将字典数据存放数Trie树中 TrieNode trie = new TrieNode(); for (String root: dictionary) { //从头开始遍历 TrieNode cur =trie; for (char letter: root.toCharArray()){ if (cur.children[letter - 'a'] == null){ cur.children[letter - 'a'] = new TrieNode(); } cur = cur.children[letter - 'a']; } cur.word = root; } // 将句子按照空格分割程单词依次判断是否在Trie树中, // 不存在使用原有单词, 完成新句子拼接 StringBuilder ans = new StringBuilder(); for (String word: sentence.split("\\s+")){ if (ans.length() > 0){ ans.append(" " ); } TrieNode cur = trie; for (char letter:word.toCharArray()){ if (cur.children[letter - 'a'] == null ||\<br> cur.word != null){ break; } cur = cur.children[letter - 'a']; } ans.append(cur.word!=null?cur.word:word); } return ans.toString(); } }
class TrieNode {
    TrieNode[] children;
    String word;
    TrieNode(){
        children = new TrieNode[26];
        /*默认初始化null
        for (int i=0; i<26; i++){
            children[i] = null;
        }
        */
    }
}

class Solution{
    public String replaceWords(List<String> dictionary, String sentence) { 
        // 将字典数据存放数Trie树中
        TrieNode trie = new TrieNode();
        for (String root: dictionary) {
            //从头开始遍历
            TrieNode cur =trie;
            for (char letter: root.toCharArray()){
                if (cur.children[letter - 'a'] == null){
                    cur.children[letter - 'a'] = new TrieNode();
                }
                cur = cur.children[letter - 'a'];
            }
            cur.word = root;
        }
        
        // 将句子按照空格分割程单词依次判断是否在Trie树中,
        // 不存在使用原有单词, 完成新句子拼接
        StringBuilder ans = new StringBuilder();
        for (String word: sentence.split("\\s+")){
            if (ans.length() > 0){
                ans.append(" " );
            }
            TrieNode cur = trie;
            for (char letter:word.toCharArray()){
                if (cur.children[letter - 'a'] == null ||\
cur.word != null){ break; } cur = cur.children[letter - 'a']; } ans.append(cur.word!=null?cur.word:word); } return ans.toString(); } }
  • python实现

这个实现使用了python中的collections 的defaultdict容器

 defaultdict内置两个属性:

  • 一个工厂函数
  • dict

这里Trie定义为一个lambda表达式 ,工厂函数为 collections.defaultdict(Trie),  trie为trie树根节点,那根节点的子节点结构也是一个工厂函数+ dict ,一直到词根的结束增加一条{‘END’:root} 记录(不一定是叶子节点,可以看到 如果词根是’cat’,  存在Key为’True’, 如果还存在catx,那么Trie还要向下扩展),如果将’cat’在添加到一个空的Trie树: 过程如下,

  1. 增加’c’ 字母, defaultdict(<function >, {‘c’: defaultdict(<function >, {…})})
  2. 增加’a’ 字母,  1. 中{ …}  内容->   {‘a’: defaultdict(<function>, {…})}
  3. 增加’t’ 字母,  2. 中{ …} 内容->    {‘t’: defaultdict(<function >, {True: ‘cat’, …})}
  4. 如果t后面还有字母增加到{…}

reduce函数实现了以上功能, 是对 每一个文根的单个字符进行处理,构造为一个包含defaultdict的defaultdict,自包含, 有点类似树节点定义。   

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
struct Node{
struct Node *left;
struct Node *right;
...
};
struct Node{ struct Node *left; struct Node *right; ... };
struct Node{
   struct Node *left;
   struct Node *right;
...
};

replace就是查找Trie的过程,找到后替换否则保持不变。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
class Solution:
def replaceWords(self, dictionary, sentence):
Trie = lambda: collections.defaultdict(Trie)
trie = Trie()
END = True
for root in dictionary:
reduce(dict.__getitem__, root, trie)[END] = root
def replace(word):
cur = trie
for letter in word:
if letter not in cur or END in cur: break;
cur = cur[letter]
return cur.get(END, word)
return " ".join(map(replace, sentence.split()))
class Solution: def replaceWords(self, dictionary, sentence): Trie = lambda: collections.defaultdict(Trie) trie = Trie() END = True for root in dictionary: reduce(dict.__getitem__, root, trie)[END] = root def replace(word): cur = trie for letter in word: if letter not in cur or END in cur: break; cur = cur[letter] return cur.get(END, word) return " ".join(map(replace, sentence.split()))
class Solution: 
    def replaceWords(self, dictionary, sentence):
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()
        END = True
        
        for root in dictionary:
            reduce(dict.__getitem__, root, trie)[END] = root
        
        def replace(word):
            cur = trie
            for letter in word:
                if letter not in cur or END in cur: break;
                cur = cur[letter]
            return cur.get(END, word)
        
        return " ".join(map(replace, sentence.split()))

 

参考及引用:

https://leetcode.com/problems/replace-words/solution/

Photo by Daniel Spase from Pexels

Comments are closed.