Question
字符串1:只含有英文字母
字符串2:含有英文字母和*,其中符号*表示匹配任意字符0或者多次,即正则表达式里面的含义。
现在给定这样的两个串,要求判断是否匹配?
bool isMatch ( const char *str1, const char *str2)
例如:str1 = “hello”, str2 = “he*o”,则二者匹配,返回true,str1 = “hello”, str2 = “he*l”,则不匹配,返回false。
Solution
关键是如何处理*,首先想到的就是回溯,在纸上画了一下得到如下算法
设输入是两个字符串 s, t, 其中t可能包含*
1.当*t不是*的时候, 就像普通的串匹配一样, 移动s和t
2.当*t是*的时候, 假设*t后面第一个不是*的字符是x, 若x是null, 直接匹配成功, 否则在s中找到当前位置后所有字符x的位置, 这时候问题转化成了t中x后的串和s中当前位置以后所有以x为开始的串的匹配问题, 递归调用即可, 其中任意一个匹配成功, 则原串匹配成功, 若都没有匹配成功则匹配失败.
3.当*s和*t其中一个是null时 跳出循环, 若此时 *t == ‘*’, 则++t 知道 t != ‘*’, 这时若 *t == 0 则代表匹配成功, 否则匹配失败。
代码如下:
#include
#include
using namespace std;
bool is_match(const char * s, const char * t)
{
while (*s && *t)
{
if (*t != '*' && *s == *t)
++s, ++t;
else if (*t != '*' && *s != *t)
return false;
else if (*t == '*')
{
do ++t; while (*t == '*');
if (*t == 0) return true;
for ( ; *s; ++s)
if (*s == *t && is_match(s+1, t+1))
return true;
return false;
}
}
while (*t == '*') ++t;
if (*s == *t) return true;
else return false;
}
int main(int argc, char * argv[])
{
if (is_match(argv[1], argv[2]))
cout << "match" << endl;
else cout << "not match" << endl;
return 0;
}
改进
上面的暴力算法如果遇到“aaaaaaaaaaaaaaaa”,“a*a*a*a*a*a*a*a*a*a*a*a”这样的输入,会达到2^n的复杂度,是无法接受的。注意到,递归搜索是有很多重复的状态,自然就想到了记忆化搜索,时间空间复杂度均为O(n^2),代码如下:
#include
#include
using namespace std;
const int MAX_LEN = 1024;
int dp[MAX_LEN][MAX_LEN];
bool is_match(int p, int q, const char * s, const char * t)
{
if (dp[p][q] >= 0) return dp[p][q];
int &ans = dp[p][q] = 0;
if (!s[p] && !t[q]) {
ans = true;
} else if (!s[p] || !t[q]) {
if (t[q] == '*') {
ans = is_match(p, q + 1, s, t);
}
} else {
if (t[q] == '*') {
ans = is_match(p + 1, q, s, t)
|| is_match(p, q + 1, s, t);
} else if (s[p] == t[q]) {
ans = is_match(p + 1, q + 1, s, t);
}
}
return ans;
}
bool is_match(const char * s, const char * t)
{
memset(dp, -1, sizeof(dp));
return is_match(0, 0, s, t);
}
int main(int argc, char * argv[])
{
if (is_match(argv[1], argv[2]))
cout << "match" << endl;
else cout << "not match" << endl;
return 0;
}
:x
没有看明白你的思路。
我认为没有要求最大或者最小匹配 所以直接字符比较就可以了 函数如下
bool is_match(const char * s, const char * t)
{
//记忆源字符串的开始位置和匹配串的开始位置
const char *srcFirst = s;
const char *mathFirst = t;
while (*s && *t)
{
//匹配到* 匹配下面一个域
if(‘*’ == *t) return is_match(s,++t);
//匹配到不一样的时 源字符串返回到开始位置+1 匹配字符串返回到开始位置
if (*t != *s){
s = srcFirst++;
t = mathFirst;
continue;
}
s++;
t++;
}
//遍历完返回
if(!*t) return true;
return false;
}
@crowsy, 这个不是和我的第一个算法一样么,都是暴力搜索;这个和普通的字符串匹配的过程不一样。普通的字符串匹配没有递归,所以只是len(s)*len(t)的复杂度。
一样? 惭愧没看懂你的。
你的似乎测试不过呀。
@crowsy, 你是说改进的算法么?不好意思改进算法原来有个地方写错了,第13行应该是 if (!s[p] && !t[q]) { 原来少了两个非号。
str1 = “hello”, str2 = “he*l” 应该是匹配的