[一道面试题]含有*的字符串匹配问题
浏览:2089次 出处信息
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可能包含* <.p>
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 则代表匹配成功, 否则匹配失败。
代码如下:
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 |
#include <cstring> #include <iostream> 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),代码如下:
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 |
#include <iostream> #include <cstring> 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 = 1; } 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; } |
建议继续学习:
- 字符串匹配那些事(一) (阅读:5831)
- 利用vim(gvim)的正则表达式实现代码自动匹配完成(等号两边数据交换) (阅读:3270)
- [正则优化] CSS选择符匹配 (阅读:2482)
- [正则优化] CSS属性选择符的匹配 (阅读:2403)
- 设计模式-自动完成 (阅读:1845)
- CSS 样式规则的匹配算法实现 (阅读:753)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:计数和排序
后一篇:独创比百度、Google分页还强的分页类 >>
文章信息
- 作者:Jackal 来源: Programming Life with Music
- 标签: 匹配
- 发布时间:2009-11-26 23:10:59
建议继续学习
近3天十大热文
- [71] Twitter/微博客的学习摘要
- [65] find命令的一点注意事项
- [64] IOS安全–浅谈关于IOS加固的几种方法
- [63] 如何拿下简短的域名
- [63] android 开发入门
- [62] Go Reflect 性能
- [61] 流程管理与用户研究
- [60] Oracle MTS模式下 进程地址与会话信
- [60] 图书馆的世界纪录
- [58] 读书笔记-壹百度:百度十年千倍的29条法则