Question

648. 单词替换

English Version

题目描述

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

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

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

 

示例 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"

 

提示：

• 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 没有前导或尾随空格。

 

解法

方法一：前缀树

我们定义前缀树的节点数据结构如下：

• children：子节点数组，长度为 $26$，每个元素为一个节点或 None
• ref：如果当前节点是一个单词的结尾，则 ref 为该单词在 dictionary 中的索引，否则为 $-1$

我们首先将 dictionary 中的单词插入到前缀树中，然后遍历 sentence 中的每个单词，查找前缀树中是否存在该单词的前缀，如果存在，则将该单词替换为前缀。

时间复杂度为 $O(\sum_{w \in dictionary} |w| + |sentence|)$，空间复杂度为 $O(\sum_{w \in dictionary} |w|)$。其中 $|w|$ 表示单词 $w$ 的长度。

class Trie:
  def __init__(self):
    self.children: List[Trie | None] = [None] * 26
    self.ref: int = -1

  def insert(self, w: str, i: int):
    node = self
    for c in w:
      idx = ord(c) - ord("a")
      if node.children[idx] is None:
        node.children[idx] = Trie()
      node = node.children[idx]
    node.ref = i

  def search(self, w: str) -> int:
    node = self
    for c in w:
      idx = ord(c) - ord("a")
      if node.children[idx] is None:
        return -1
      node = node.children[idx]
      if node.ref != -1:
        return node.ref
    return -1


class Solution:
  def replaceWords(self, dictionary: List[str], sentence: str) -> str:
    trie = Trie()
    for i, w in enumerate(dictionary):
      trie.insert(w, i)
    ans = []
    for w in sentence.split():
      idx = trie.search(w)
      ans.append(dictionary[idx] if idx != -1 else w)
    return " ".join(ans)

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 Trie {
private:
  Trie* children[26];
  int ref;

public:
  Trie()
    : ref(-1) {
    memset(children, 0, sizeof(children));
  }

  void insert(const string& w, int i) {
    Trie* node = this;
    for (auto& c : w) {
      int idx = c - 'a';
      if (!node->children[idx]) {
        node->children[idx] = new Trie();
      }
      node = node->children[idx];
    }
    node->ref = i;
  }

  int search(const string& w) {
    Trie* node = this;
    for (auto& c : w) {
      int idx = c - 'a';
      if (!node->children[idx]) {
        return -1;
      }
      node = node->children[idx];
      if (node->ref != -1) {
        return node->ref;
      }
    }
    return -1;
  }
};

class Solution {
public:
  string replaceWords(vector<string>& dictionary, string sentence) {
    Trie* trie = new Trie();
    for (int i = 0; i < dictionary.size(); ++i) {
      trie->insert(dictionary[i], i);
    }
    stringstream ss(sentence);
    string w;
    string ans;
    while (ss >> w) {
      int idx = trie->search(w);
      ans += (idx == -1 ? w : dictionary[idx]) + " ";
    }
    ans.pop_back();
    return ans;
  }
};

type Trie struct {
  children [26]*Trie
  ref    int
}

func newTrie() *Trie {
  return &Trie{ref: -1}
}

func (this *Trie) insert(w string, i int) {
  node := this
  for _, c := range w {
    idx := c - 'a'
    if node.children[idx] == nil {
      node.children[idx] = newTrie()
    }
    node = node.children[idx]
  }
  node.ref = i
}

func (this *Trie) search(w string) int {
  node := this
  for _, c := range w {
    idx := c - 'a'
    if node.children[idx] == nil {
      return -1
    }
    node = node.children[idx]
    if node.ref != -1 {
      return node.ref
    }
  }
  return -1
}

func replaceWords(dictionary []string, sentence string) string {
  trie := newTrie()
  for i, w := range dictionary {
    trie.insert(w, i)
  }
  ans := strings.Builder{}
  for _, w := range strings.Split(sentence, " ") {
    if idx := trie.search(w); idx != -1 {
      ans.WriteString(dictionary[idx])
    } else {
      ans.WriteString(w)
    }
    ans.WriteByte(' ')
  }
  return ans.String()[:ans.Len()-1]
}

class Trie {
  private children: Trie[];
  private ref: number;

  constructor() {
    this.children = new Array<Trie>(26);
    this.ref = -1;
  }

  public insert(w: string, i: number) {
    let node: Trie = this;
    for (const c of w) {
      const idx = c.charCodeAt(0) - 97;
      if (!node.children[idx]) {
        node.children[idx] = new Trie();
      }
      node = node.children[idx];
    }
    node.ref = i;
  }

  public search(w: string): number {
    let node: Trie = this;
    for (const c of w) {
      const idx = c.charCodeAt(0) - 97;
      if (!node.children[idx]) {
        return -1;
      }
      node = node.children[idx];
      if (node.ref !== -1) {
        return node.ref;
      }
    }
    return -1;
  }
}

function replaceWords(dictionary: string[], sentence: string): string {
  const trie = new Trie();
  for (let i = 0; i < dictionary.length; i++) {
    trie.insert(dictionary[i], i);
  }
  return sentence
    .split(' ')
    .map(w => {
      const idx = trie.search(w);
      return idx !== -1 ? dictionary[idx] : w;
    })
    .join(' ');
}

方法二

class Trie {
  private Trie[] children = new Trie[26];
  private int ref = -1;

  public void insert(String w, int i) {
    Trie node = this;
    for (int j = 0; j < w.length(); ++j) {
      int idx = w.charAt(j) - 'a';
      if (node.children[idx] == null) {
        node.children[idx] = new Trie();
      }
      node = node.children[idx];
    }
    node.ref = i;
  }

  public int search(String w) {
    Trie node = this;
    for (int j = 0; j < w.length(); ++j) {
      int idx = w.charAt(j) - 'a';
      if (node.children[idx] == null) {
        return -1;
      }
      node = node.children[idx];
      if (node.ref != -1) {
        return node.ref;
      }
    }
    return -1;
  }
}

class Solution {
  public String replaceWords(List<String> dictionary, String sentence) {
    Trie trie = new Trie();
    for (int i = 0; i < dictionary.size(); ++i) {
      trie.insert(dictionary.get(i), i);
    }
    List<String> ans = new ArrayList<>();
    for (String w : sentence.split("\\s")) {
      int idx = trie.search(w);
      ans.add(idx == -1 ? w : dictionary.get(idx));
    }
    return String.join(" ", ans);
  }
}