LeetCode 211. 添加与搜索单词 - 数据结构设计
原题链接
中等
作者:
我是java同学
,
2023-10-04 12:58:42
,
所有人可见
,
阅读 60
static const int N = 250000, M = 26;
static int son[N][M];
static bool is_end[N];
static int idx;
class WordDictionary {
public:
WordDictionary() {
memset(son, 0, sizeof son);
memset(is_end, 0, sizeof is_end);
idx = 0;
}
void addWord(string word) {
int p = 0;
for (int i = 0; i < word.size(); i ++ ) {
int u = word[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
is_end[p] = true;
}
bool search(string word) {
return dfs(word, 0, 0);
}
bool dfs(string s, int p, int u) {
if (u == s.size()) return is_end[p];
char c = s[u];
if (c == '.') {
for (int i = 0; i < 26; i ++ )
if (son[p][i] && dfs(s, son[p][i], u + 1))
return true;
return false;
} else {
int t = c - 'a';
if (!son[p][t]) return false;
return dfs(s, son[p][t], u + 1);
}
}
};