题目描述：
如果可以将小写字母插入模式串pattern得到query，那么返回true。
数据范围：
$1\le n \le 100, 1\le s.length \le 100, 1\le t.length\ le 100$
题解：
使用双指针， $l1$ 指向pattern， $l2$ 指向query。
- 如果二者相等，则继续移动；
- 如果不匹配
- $l1$ 当前为大写，返回
false - $l1$ 当前为小写，忽略不匹配，即移动 $l1$ 。
- 如果 $l2$ 到达末尾， $l1$ 还未到达末尾，需要对 $l1$ 剩余字符判断，如果剩余字符有大写则返回
false；否则返回true。
也可以使用字典树，不过有点大材小用。
将模式串插入 $trie$ ，然后对每一个 $query$ 在 $trie$ 上查询，如果匹配就移动，不匹配如果是小写字符就continue，否则返回false。最后返回 $exist[now]$ 。
需要注意的是，如果使用 $trie$ ，因为存在大写和小写，需要把 $M$ 开到'z' - 'A' + 1。因为字符集大小为 'z' - 'A' + 1。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
bool check(string query, string &pattern)
{
int size1 = query.size(), size2 = pattern.size();
int l1 = 0, l2 = 0;
while (l1 < size1 && l2 < size2)
{
if (query[l1] == pattern[l2])
{
++l1;
++l2;
}
else if (isupper(query[l1]))
return false;
else
{
l1++;
}
}
while (l1 < size1)
if (isupper(query[l1++]))
return false;
return l2 == size2;
}
vector<bool> camelMatch(vector<string> &queries, string pattern)
{
vector<bool> ans;
for (auto &s : queries)
{
ans.emplace_back(check(s, pattern));
}
return ans;
}
};
|
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
struct Trie
{
const static int Len = 100 * 30;
const static int M = 'z' - 'A';
int nex[Len][M] = {}, cnt = 0;
bool exist[Len] = {};
void insert(string s)
{
int now = 0;
for (int i = 0; i < s.length(); ++i)
{
int ch = s[i] - 'A';
if (!nex[now][ch])
nex[now][ch] = ++cnt;
now = nex[now][ch];
}
exist[now] = true;
}
bool query(string s)
{
int now = 0;
for (int i = 0; i < s.length(); ++i)
{
int ch = s[i] - 'A';
if (nex[now][ch])
now = nex[now][ch];
else if (isupper(s[i]))
return false;
else
continue;
}
return exist[now];
}
};
vector<bool> camelMatch(vector<string> &queries, string pattern)
{
Trie trie;
trie.insert(pattern);
vector<bool> ans;
for (auto &s : queries)
{
ans.emplace_back(trie.query(s));
}
return ans;
}
};
|