技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> [一道面试题]含有*的字符串匹配问题

[一道面试题]含有*的字符串匹配问题

浏览:2073次  出处信息

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;
}

建议继续学习:

  1. 字符串匹配那些事(一)    (阅读:5741)
  2. 利用vim(gvim)的正则表达式实现代码自动匹配完成(等号两边数据交换)    (阅读:3248)
  3. [正则优化] CSS选择符匹配    (阅读:2458)
  4. [正则优化] CSS属性选择符的匹配    (阅读:2376)
  5. 设计模式-自动完成    (阅读:1762)
  6. CSS 样式规则的匹配算法实现    (阅读:730)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1