Question

剑指 Offer II 063. 替换单词

题目描述

在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

需要输出替换之后的句子。

 

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

示例 3：

输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
输出："a a a a a a a a bbb baba a"

示例 4：

输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 5：

输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
输出："it is ab that this solution is ac"

 

提示：

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] 仅由小写字母组成。
• 1 <= sentence.length <= 10^6
• sentence 仅由小写字母和空格组成。
• sentence 中单词的总量在范围 [1, 1000] 内。
• sentence 中每个单词的长度在范围 [1, 1000] 内。
• sentence 中单词之间由一个空格隔开。
• sentence 没有前导或尾随空格。

 

注意：本题与主站 648 题相同： https://leetcode.cn/problems/replace-words/

解法

方法一：哈希表

class Solution:
  def replaceWords(self, dictionary: List[str], sentence: str) -> str:
    s = set(dictionary)
    words = sentence.split()
    for i, word in enumerate(words):
      for j in range(1, len(word) + 1):
        if word[:j] in s:
          words[i] = word[:j]
          break
    return ' '.join(words)

class Solution {
  public String replaceWords(List<String> dictionary, String sentence) {
    Set<String> s = new HashSet<>(dictionary);
    String[] words = sentence.split(" ");
    for (int i = 0; i < words.length; ++i) {
      String word = words[i];
      for (int j = 1; j <= word.length(); ++j) {
        String t = word.substring(0, j);
        if (s.contains(t)) {
          words[i] = t;
          break;
        }
      }
    }
    return String.join(" ", words);
  }
}

class Solution {
public:
  string replaceWords(vector<string>& dictionary, string sentence) {
    unordered_set<string> s(dictionary.begin(), dictionary.end());
    istringstream is(sentence);
    vector<string> words;
    string ss;
    while (is >> ss) words.push_back(ss);
    for (int i = 0; i < words.size(); ++i) {
      string word = words[i];
      for (int j = 1; j <= word.size(); ++j) {
        string t = word.substr(0, j);
        if (s.count(t)) {
          words[i] = t;
          break;
        }
      }
    }
    string ans = "";
    for (string& word : words) ans += word + " ";
    ans.pop_back();
    return ans;
  }
};

func replaceWords(dictionary []string, sentence string) string {
  s := map[string]bool{}
  for _, v := range dictionary {
    s[v] = true
  }
  words := strings.Split(sentence, " ")
  for i, word := range words {
    for j := 1; j <= len(word); j++ {
      t := word[:j]
      if s[t] {
        words[i] = t
        break
      }
    }
  }
  return strings.Join(words, " ")
}

方法二：前缀树

class Trie:
  def __init__(self):
    self.children = [None] * 26
    self.v = None

  def insert(self, word):
    node = self
    for c in word:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        node.children[idx] = Trie()
      node = node.children[idx]
    node.v = word

  def search(self, word):
    node = self
    for c in word:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        break
      node = node.children[idx]
      if node.v:
        return node.v
    return word


class Solution:
  def replaceWords(self, dictionary: List[str], sentence: str) -> str:
    trie = Trie()
    for v in dictionary:
      trie.insert(v)
    return ' '.join(trie.search(v) for v in sentence.split())

class Trie {
  Trie[] children = new Trie[26];
  String v;

  void insert(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      c -= 'a';
      if (node.children[c] == null) {
        node.children[c] = new Trie();
      }
      node = node.children[c];
    }
    node.v = word;
  }

  String search(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      c -= 'a';
      if (node.children[c] == null) {
        return word;
      }
      node = node.children[c];
      if (node.v != null) {
        return node.v;
      }
    }
    return word;
  }
}

class Solution {
  public String replaceWords(List<String> dictionary, String sentence) {
    Trie trie = new Trie();
    for (String v : dictionary) {
      trie.insert(v);
    }
    List<String> ans = new ArrayList<>();
    for (String v : sentence.split("\\s")) {
      ans.add(trie.search(v));
    }
    return String.join(" ", ans);
  }
}

class Trie {
public:
  vector<Trie*> children;
  string v;
  Trie()
    : children(26)
    , v("") {}

  void insert(string word) {
    Trie* node = this;
    for (char c : word) {
      c -= 'a';
      if (!node->children[c]) node->children[c] = new Trie();
      node = node->children[c];
    }
    node->v = word;
  }

  string search(string word) {
    Trie* node = this;
    for (char c : word) {
      c -= 'a';
      if (!node->children[c]) break;
      node = node->children[c];
      if (node->v != "") return node->v;
    }
    return word;
  }
};

class Solution {
public:
  string replaceWords(vector<string>& dictionary, string sentence) {
    Trie* trie = new Trie();
    for (auto& v : dictionary) trie->insert(v);
    string ans = "";
    istringstream is(sentence);
    vector<string> ss;
    string s;
    while (is >> s) ss.push_back(s);
    for (auto word : ss) ans += trie->search(word) + " ";
    ans.pop_back();
    return ans;
  }
};

type Trie struct {
  children [26]*Trie
  v    string
}

func newTrie() *Trie {
  return &Trie{}
}
func (this *Trie) insert(word string) {
  node := this
  for _, c := range word {
    c -= 'a'
    if node.children[c] == nil {
      node.children[c] = newTrie()
    }
    node = node.children[c]
  }
  node.v = word
}

func (this *Trie) search(word string) string {
  node := this
  for _, c := range word {
    c -= 'a'
    if node.children[c] == nil {
      break
    }
    node = node.children[c]
    if node.v != "" {
      return node.v
    }
  }
  return word
}

func replaceWords(dictionary []string, sentence string) string {
  trie := newTrie()
  for _, v := range dictionary {
    trie.insert(v)
  }
  var ans []string
  for _, v := range strings.Split(sentence, " ") {
    ans = append(ans, trie.search(v))
  }
  return strings.Join(ans, " ")
}