算法-字符串模糊匹配-Google kickstart2017 Round A - Problem B

题目描述

给定两个字符串,判断两个字符串是否匹配。字符串中出现的“*”可以匹配0-4个任意字符。比如如下输入样例:

3
****
It
Shakes*e
S*speare
Shakes*e
*peare

对应的输出为:

Case #1: TRUE
Case #2: TRUE
Case #3: FALSE

可能解法

解决思路如下:

  1. 将原始字符串进行扩展,一个“*”替换成“****”;
  2. 建立二维数组match[i][j],表示第一个字符串的[0,i]子串与第二个字符串的[0,j]是否匹配,由于*的存在,需要注意match数组存放的是;
  3. 动态规划求解,数组match的最后一个元素表示了是否匹配。动态规划的更新需要考虑一下两点:
    • *可以匹配任何字符,但同时也可以不存在;
    • 初值设置应该考虑特殊输入,比如空的字符串。
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
#include<iostream>
#include<string>
using namespace std;
int main()
{
int T;
cin >> T;
for (int Case = 1; Case <= T; Case++) {
string first;
string second;
cin >> first;
cin >> second;
string firstc = "#";
string secondc = "#";
for (int i = 0;i < first.size();i++){
if (first[i] == '*')
firstc += "****";
else
firstc += first[i];
}
for (int i = 0;i < second.size();i++){
if (second[i] == '*')
secondc += "****";
else
secondc += second[i];
}
int m = firstc.size();
int n = secondc.size();
int match[m][n];
match[0][0] = 1;
for (int i = 0;i < m;i++){
for (int j = 0; j < n; j++){
if (i == 0 && j == 0){
match[i][j] = 1;
}
else if (i == 0){
match[i][j] = (secondc[j] == '*')?match[i][j-1]:0;
}
else if (j == 0){
match[i][j] = (firstc[i] == '*')?match[i-1][j]:0;
}
else if (i > 0 && j > 0) {
match[i][j] =
match[i - 1][j - 1] && (firstc[i] == '*' || secondc[j] == '*' || firstc[i] == secondc[j]);
if (firstc[i] == '*')
match[i][j] = match[i][j] || match[i - 1][j];
if (secondc[j] == '*')
match[i][j] = match[i][j] || match[i][j - 1];
}
}
}
if(match[m-1][n-1])
cout << "Case #" << Case << ": " << "TRUE" << endl;
else
cout << "Case #" << Case << ": " << "FALSE" << endl;
}
return 0;
}

复杂度分析

单次算法时间复杂度为$\mathcal{O}(n^2)$,空间复杂度也为$\mathcal{O}(n^2)$。

文章目录
  1. 1. 题目描述
  2. 2. 可能解法
  3. 3. 复杂度分析
|