Add and Search Word - Data structure design

發表於   |   分類於

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

1
2
void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

回溯法解。注意需要剪枝，不然会超时。

首先上没有剪枝的版本，这个代码超时了：

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
58
59
60
61
62
class WordDictionary {
public:

	map<string, int> datas;
	// Adds a word into the data structure.
	void addWord(string word) {
		auto it = datas.find(word);
		if (it == datas.end())
		{
			pair<string, int> p(word, 1);
			datas.insert(p);
		}
		else
		{
			it->second += 1;
		}
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool search(string word) {
		bool r = false;
		string st;
		solve(r, st, word, 0);
		return r;
	}

	void solve(bool& r, string& st, string& word, int index)
	{
		int pos = index;
		for (; pos < word.length(); ++pos)
		{
			if (word[pos] == '.')
			{
				break;
			}
			st.push_back(word[pos]);
		}

		if (st.length() == word.length())
		{
			if (r == false)
			{
				r = (datas.find(st) != datas.end());
			}
			return;
		}

		for (int i = 'a'; i <= 'z'; ++i)
		{
			st.push_back((char)i);
			solve(r, st, word, pos + 1);
			if (r) return;
			int l = st.length() - pos;
			while (l > 0)
			{
				st.pop_back();
				--l;
			}
		}
	}
};

然后是AC了的剪枝版本。剪枝过程使用了字典树，然后就是Check函数的三种返回值需要注意；字典树节点中的BOOL成员表明该字符是否属于一个字符串的终结字符。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class WordDictionary {
public:

	struct Node
	{
		char c;
		bool bstr;
		Node* children[26];
		Node()
		{
			for (int i = 0; i < 26; ++i)
				children[i] = NULL;
			bstr = false;
		}
		Node(char ch):c(ch)
		{
			for (int i = 0; i < 26; ++i)
				children[i] = NULL;
			bstr = false;
		}
	}root;
	// Adds a word into the data structure.
	void addWord(string word) {
		Node* pRoot = &root;
		for (int i = 0; i < word.length(); ++i)
		{
			if (pRoot->children[word[i] - 'a'] == NULL)
			{
				pRoot->children[word[i] - 'a'] = new Node(word[i]);
			}
			pRoot = pRoot->children[word[i] - 'a'];
			if (i + 1 == word.length())
				pRoot->bstr = true;
		}
	}

	int check(string& s)
	{
		Node* pRoot = &root;
		Node* eNode = NULL;
		for (int i = 0; i < s.length(); ++i)
		{
			pRoot = pRoot->children[s[i] - 'a'];
			if (pRoot == NULL)
				return 0;
			if (i + 1 == s.length())
				eNode = pRoot;
		}
		if (eNode->bstr) return 1;
		return -1;
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool search(string word) {
		bool r = false;
		string st;
		solve(r, st, word, 0);
		return r;
	}

	void solve(bool& r, string& st, string& word, int index)
	{
		int pos = index;
		for (; pos < word.length(); ++pos)
		{
			if (word[pos] == '.')
			{
				break;
			}
			st.push_back(word[pos]);
		}

		if (st.length() == word.length())
		{
			if (r == false)
			{
				r =  (1 == check(st));
			}
			return;
		}

		for (int i = 'a'; i <= 'z'; ++i)
		{
			st.push_back((char)i);
			if (0 == check(st))
			{
				st.pop_back();
				continue;
			}
			solve(r, st, word, pos + 1);
			if (r) return;
			int l = st.length() - pos;
			while (l > 0)
			{
				st.pop_back();
				--l;
			}
		}
	}
};