本题可以用字典树和深度优先搜索来解决
一、题目
设计一个支持以下两种操作的数据结构：
void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
示例:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
说明:
你可以假设所有单词都是由小写字母 a-z 组成的。
二、思路
总的来说，我们要设计的程序需要实现两个功能：插入单词和搜索单词。
我们当然可以用一个List<String>来保存每个插入的单词，假设我们要插入n个单词，每个每个单词长度为m。那么，插入一个单词的时间复杂度是O(1)，搜索一个单词的时间复杂度是O（m*n）。搜索的时间复杂度太高了。
2.1 字典树
我们可以使用这样一种数据结构：字典树。
字典树，又称为单词查找树，Tire数，是一种树形结构，它是一种哈希树的变种。结构如下图所示。
image.png
2.2 字典树的性质
字典树是一个树形结构。
根节点不包含字符，除根结点之外每一个子结点都包含一个字符。
从根节点到某一结点，路径上经过的字符连接起来，就是该结点对应的字符串。
image.png
2.3子结点的应用
字典树中的公共前缀可以减少查找次数，查找效率比哈希树高。
字典树可以应用于统计、排序、保存大量字符串，经常被搜索引擎系统用于文本词频统计。
2.4应用字典树来解题
2.4.1 节点
我设计的字典树结点如下：
class TreeNode {
boolean hasWord = false; //本是否有字符
boolean isEnd = false; //本节点是不是某个单词轨迹的最后一个节点
TreeNode[] childs; //子结点数组
TreeNode() {
childs = new TreeNode[26];
}
}
2.4.2 插入单词
插入单词比较简单。根据字符计算字符在子结点数组中的位置，将字符插入对应位置。不断循环，完成字符插入。
/** Adds a word into the data structure. */
public void addWord(String word) {
if (word == null || word.length() == 0) {
return;
}
cur = head;
for (int i = 0; i < word.length(); i++) { //遍历字符，将每个字符插入到适合的位置
char tempChar = word.charAt(i);
int tempIndex = tempChar - 'a'; //计算字符在子结点数组中的位置
if (cur.childs[tempIndex] == null) {
cur.childs[tempIndex] = new TreeNode();
}
cur.childs[tempIndex].hasWord = true; //设置标志位，表明该节点有字符存在
cur = cur.childs[tempIndex];
}
cur.isEnd = true; //字符轨迹的最后一个节点标记位end
}
2.4.3 搜索单词
搜索单词就是用树的深度优先搜索。我使用的是递归实现的，你也可以使用栈来实现。题目中还有一个条件是 . 可以代表任意字符，这也是我们需要考虑的一个方面，就是如果被搜索的单词的最后一个字符是 . 的话，我们就需要找到当前节点的所有子节点是不是有end == true。
private boolean SearchLoop(String word, TreeNode tempNode) {
if (word == null || word.length() == 0) {
return true;
}
char tempChar = word.charAt(0);
int tempIndex = tempChar - 'a'; //计算位置
if(tempIndex < 0) { //tempIndex<0就表明当前字符是 .
if (word.length() == 1) { //如果当前字符是被搜索单词的最后一个字符
for (int i = 0; i < 26; i++) {
if (tempNode.childs[i] != null && tempNode.childs[i].isEnd == true) {
return true;
}
}
return false;
}else { //如果当前字符不是被搜索单词的最后一个字符，进行深度优先搜索
for (int i = 0; i < 26; i++) {
if (tempNode.childs[i] != null) {
if (SearchLoop(word.substring(1),tempNode.childs[i])) {
return true;
}
}
}
return false;
}
} else if (tempNode.childs[tempIndex] != null && tempNode.childs[tempIndex].hasWord == true) { //如果对应tempIndex位置有单词
if (word.length() == 1){ //如果是最后一个字符，查看该节点是不是某个单词的最后一个节点
return tempNode.childs[tempIndex].isEnd;
} else { //如果不是最后一个字符，继续深度优先搜索
return SearchLoop(word.substring(1),tempNode.childs[tempIndex]);
}
} else { //如果对应tempIndex位置没有单词,搜索失败。
return false;
}
}
代码
java 有的时候超时，有的时候又击败90%的人，奇怪。
class WordDictionary {
class TreeNode {
boolean hasWord = false; //本是否有字符
boolean isEnd = false; //本节点是不是某个单词轨迹的最后一个节点
TreeNode[] childs; //子结点数组
TreeNode() {
childs = new TreeNode[26];
}
}
TreeNode head = null;
TreeNode cur = null;
/** Initialize your data structure here. */
public WordDictionary() {
head = new TreeNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
if (word == null || word.length() == 0) {
return;
}
cur = head;
for (int i = 0; i < word.length(); i++) { //遍历字符，将每个字符插入到适合的位置
char tempChar = word.charAt(i);
int tempIndex = tempChar - 'a'; //计算字符在子结点数组中的位置
if (cur.childs[tempIndex] == null) {
cur.childs[tempIndex] = new TreeNode();
}
cur.childs[tempIndex].hasWord = true; //设置标志位，表明该节点有字符存在
cur = cur.childs[tempIndex];
}
cur.isEnd = true; //字符轨迹的最后一个节点标记位end
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
cur = head;
return SearchLoop(word,cur);
}
private boolean SearchLoop(String word, TreeNode tempNode) {
if (word == null || word.length() == 0) {
return true;
}
char tempChar = word.charAt(0);
int tempIndex = tempChar - 'a'; //计算位置
if(tempIndex < 0) { //tempIndex<0就表明当前字符是 .
if (word.length() == 1) { //如果当前字符是被搜索单词的最后一个字符
for (int i = 0; i < 26; i++) {
if (tempNode.childs[i] != null && tempNode.childs[i].isEnd == true) {
return true;
}
}
return false;
}else { //如果当前字符不是被搜索单词的最后一个字符，进行深度优先搜索
for (int i = 0; i < 26; i++) {
if (tempNode.childs[i] != null) {
if (SearchLoop(word.substring(1),tempNode.childs[i])) {
return true;
}
}
}
return false;
}
} else if (tempNode.childs[tempIndex] != null && tempNode.childs[tempIndex].hasWord == true) { //如果对应tempIndex位置有单词
if (word.length() == 1){ //如果是最后一个字符，查看该节点是不是某个单词的最后一个节点
return tempNode.childs[tempIndex].isEnd;
} else { //如果不是最后一个字符，继续深度优先搜索
return SearchLoop(word.substring(1),tempNode.childs[tempIndex]);
}
} else { //如果对应tempIndex位置没有单词,搜索失败。
return false;
}
}
}
网友评论