跳转至

648. 单词替换

题目描述

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

现在，给定一个由许多 词根 组成的词典 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 <= 106
  • 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\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Trie {
    #children: Record<string, Trie> = {};
    #ref = -1;

    insert(w: string, i: number) {
        let node: Trie = this;
        for (const c of w) {
            node.#children[c] ??= new Trie();
            node = node.#children[c];
        }
        node.#ref = i;
    }

    search(w: string): number {
        let node: Trie = this;
        for (const c of w) {
            if (!node.#children[c]) {
                return -1;
            }
            node = node.#children[c];
            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(' ');
}

方法二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function replaceWords(dictionary: string[], sentence: string): string {
    const words = sentence.split(' ');
    const trie: Trie = {};
    const TERMINAL_MARK = 'TERMINAL_MARK';

    for (const s of dictionary) {
        let t = trie;

        for (const ch of s) {
            t[ch] ??= {};
            t = t[ch] as Trie_;
        }
        t[TERMINAL_MARK] = TERMINAL_MARK;
    }

    for (let i = 0; i < words.length; i++) {
        const s = words[i];
        let t = trie;

        for (let j = 0; j < s.length; j++) {
            const ch = s[j];

            if (!t[ch]) break;

            if ((t[ch] as Trie_)[TERMINAL_MARK]) {
                words[i] = s.slice(0, j + 1);
                break;
            }
            t = t[ch] as Trie_;
        }
    }

    return words.join(' ');
}

// prettier-ignore
type Trie = { [key: string]: Trie} | string
type Trie_ = Exclude<Trie, string>;

评论