【算法】多串匹配问题
问题描述
给定一个字符串数组 words 和一个待匹配字符串 str，判断 str 是否存在于 words 中。
示例 1
1Input:
2words = ["face", "fell", "fear", "fire", "above", "about"]
3str = "face"
4
5Output:
6true
示例 2
1Input:
2words = ["face", "fell", "fear", "fire", "above", "about"]
3str = "few"
4
5Output:
6false
题解
下面依次介绍朴素算法、哈希集合和前缀树的算法来解决这个问题。
朴素算法
依次遍历数组中的每个字符串，与待匹配串做比较，若两串相等则代表 str 是否存在于 words 中。
1boolean judge(List<String> words, String str) {
2 for (String word : words) {
3 // 遍历数组中的每个字符串，如果相等证明 str 存在于 words 中
4 if (isEqual(word, str)) {
5 return true;
6 }
7 }
8 return false;
9}
10
11boolean isEqual(String s1, String s2) {
12 if (s1.length() != s2.length()) return false;
13 for (int i = 0; i < s1.length(); ++i) {
14 if (s1.charAt(i) != s2.charAt(i)) {
15 retrun false;
16 }
17 }
18 return true;
19}
朴素算法的时间复杂度是 $O(mn)$，其中 $n$ 是 words 数组中字符串的数量，$m$ 是字符串的平均长度。在最坏情况下，需要遍历整个 words 数组并比较每个字符串与 str 的每个字符，当 words 数组规模较大时性能非常低。
哈希集合
待补齐
1boolean judge(List<String> words, String str) {
2 Set<String> set = new HashSet();
3 for (String word : words) {
4 set.add(word);
5 }
6
7 return set.contains(str);
8}
哈希集合的时间复杂度是 $O(n)$，其中 $n$ 是 words 数组中字符串的数量，当 words 数组规模较大时性能较低。
前缀树
将字符串数组中的将每个字符串拆分为字符序列，并将其存储在树的节点中，每个节点都包含一个字符以及指向其子节点的指针。通过沿着树的路径从根节点到叶节点，可以构建出一条完整的字符串。
对于给定的输入：
1Input:
2words = ["face", "fell", "fear", "fire", "above", "about"]
3str = "few"
可以构造出一颗前缀树：
代码实现是：
1typedef struct TreeNode {
2 char val;
3 struct TreeNode[] children;
4} PrefixTree;
5
6PrefixTree buildTree(char[] str, int n) {
7
8}
9
10void append(PrefixTree root, char[] str, int n) {
11
12}