211. 添加与搜索单词 - 数据结构设计

题目描述

设计一个词典类 WordDictionary，可以往里添加单词，也可以查询某个模式能否匹配到已添加的单词。

- WordDictionary()：创建空词典。 - void addWord(word)：把 word 加入词典。 - bool search(word)：如果词典里有某个单词能与 word 匹配，返回 true，否则返回 false。

查询串 word 中可能出现 '.'，它可以匹配任意一个字母。匹配要求长度相同，并且每个位置都对得上。

示例 1

输入：操作 = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
参数 = [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：[null,null,null,null,false,true,true,true]

解释：词典中有 bad、dad、mad："pad" 不存在；"bad" 存在；".ad" 能匹配三者；"b.." 能匹配 bad。

数据范围

1 <= word.length <= 25
addWord 的 word 只含小写英文字母。
search 的 word 由 '.' 或小写英文字母组成。
addWord 和 search 合计最多调用 10^4 次。

解题思路

用字典树（Trie）存所有单词：每个节点是“字母 → 孩子”的映射，单词结尾打上标记。addWord 沿路径走，缺的孩子就新建。search 用 dfs(node, i)：i 到达末尾时看 node 是否是单词结尾；普通字母只走对应的孩子；遇到 . 则对每个孩子递归，只要有一个返回 true 就成功。

为什么正确

dfs(node, i) 为真，当且仅当从 node 出发存在一条路径匹配 word[i:]，且终点是某个单词的结尾。

复杂度分析

addWord O(L)；search 无通配符时 O(L)，最坏 O(26^k · L)（k 为点的个数）；空间 O(所有单词总长)。

易错点

走完模式后必须检查结尾标记：只插入 apple 时 search("app") 应为 false。另外通配符的某个分支失败后要继续试其它孩子，不能直接返回 false。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return '$' in node
            ch = word[i]
            if ch == '.':
                return any(dfs(child, i + 1) for k, child in node.items() if k != '$')
            if ch not in node:
                return False
            return dfs(node[ch], i + 1)
        return dfs(self.root, 0)

class WordDictionary {
    private static class Node { Node[] ch = new Node[26]; boolean end; }
    private final Node root = new Node();

    public WordDictionary() {
    }

    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            if (node.ch[c - 'a'] == null) node.ch[c - 'a'] = new Node();
            node = node.ch[c - 'a'];
        }
        node.end = true;
    }

    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(Node node, String w, int i) {
        if (i == w.length())
            return node.end;
        char c = w.charAt(i);
        if (c == '.') {
            for (Node child : node.ch)
                if (child != null && dfs(child, w, i + 1)) return true;
            return false;
        }
        if (node.ch[c - 'a'] == null)
            return false;
        return dfs(node.ch[c - 'a'], w, i + 1);
    }
}

class WordDictionary {
    struct Node { Node* ch[26] = {}; bool end = false; };
    Node* root;
    bool dfs(Node* node, const string& w, int i) {
        if (i == (int)w.size())
            return node->end;
        char c = w[i];
        if (c == '.') {
            for (Node* child : node->ch)
                if (child && dfs(child, w, i + 1)) return true;
            return false;
        }
        if (!node->ch[c - 'a'])
            return false;
        return dfs(node->ch[c - 'a'], w, i + 1);
    }
public:
    WordDictionary() : root(new Node()) {}

    void addWord(string word) {
        Node* node = root;
        for (char c : word) {
            if (!node->ch[c - 'a']) node->ch[c - 'a'] = new Node();
            node = node->ch[c - 'a'];
        }
        node->end = true;
    }

    bool search(string word) {
        return dfs(root, word, 0);
    }
};

type trieNode struct {
	ch  [26]*trieNode
	end bool
}

type WordDictionary struct {
	root *trieNode
}

func Constructor() WordDictionary {
	return WordDictionary{root: &trieNode{}}
}

func (this *WordDictionary) AddWord(word string) {
	node := this.root
	for _, c := range word {
		if node.ch[c-'a'] == nil {
			node.ch[c-'a'] = &trieNode{}
		}
		node = node.ch[c-'a']
	}
	node.end = true
}

func (this *WordDictionary) Search(word string) bool {
	var dfs func(node *trieNode, i int) bool
	dfs = func(node *trieNode, i int) bool {
		if i == len(word) {
			return node.end
		}
		c := word[i]
		if c == '.' {
			for _, child := range node.ch {
				if child != nil && dfs(child, i+1) {
					return true
				}
			}
			return false
		}
		if node.ch[c-'a'] == nil {
			return false
		}
		return dfs(node.ch[c-'a'], i+1)
	}
	return dfs(this.root, 0)
}

var WordDictionary = function() {
    this.root = {};
};

WordDictionary.prototype.addWord = function(word) {
    let node = this.root;
    for (const ch of word) {
        node = node[ch] || (node[ch] = {});
    }
    node.$ = true;
};

WordDictionary.prototype.search = function(word) {
    const dfs = (node, i) => {
        if (i === word.length)
            return node.$ === true;
        const ch = word[i];
        if (ch === '.')
            return Object.keys(node).some(k => k !== '$' && dfs(node[k], i + 1));
        if (!node[ch])
            return false;
        return dfs(node[ch], i + 1);
    };
    return dfs(this.root, 0);
};

type Trie211 = { [k: string]: any };

class WordDictionary {
    private root: Trie211;

    constructor() {
        this.root = {};
    }

    addWord(word: string): void {
        let node = this.root;
        for (const ch of word) {
            node = node[ch] || (node[ch] = {});
        }
        node.$ = true;
    }

    search(word: string): boolean {
        const dfs = (node: Trie211, i: number): boolean => {
            if (i === word.length)
                return node.$ === true;
            const ch = word[i];
            if (ch === '.')
                return Object.keys(node).some(k => k !== '$' && dfs(node[k], i + 1));
            if (!node[ch])
                return false;
            return dfs(node[ch], i + 1);
        };
        return dfs(this.root, 0);
    }
}

载入编辑器，自己跑一遍 →

设计专题的其他题目

查看设计全部题目 →