注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex44 Wildcard Matching  

2015-05-26 22:37:51|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
这个比正则表达式 ex10好理解一些,而且“*”是匹配任意字符,而不是前面的字符,我写了一个递归,可惜oj最后说超时了,我觉得应该是对的。

class Solution {
public:
bool isMatch(string s, string p) {
int len1 = s.length();
int len2 = p.length();
if (len1 == 0 && len2 != 0)
return false;
if (len2 == 0 && len1 != 0)
return false;
if (len1 == len2&&len1 == 0)
return true;

bool result;
string newP = removeRepeat(p);
result = traverse(s,0,newP,0);
return result;
}
string removeRepeat(string &str)
{
int ps = 0;
int len = str.length();
string res;
int i = 0;
while (i < len)
{
if (str[i] != '*')
{
res.push_back(str[i]);
i++;
}
else
{
res.push_back(str[i]);
while ((i+1)<len&&str[i + 1] == '*')
i++;
i++;

}
}
return res;
}
bool traverse(string a,int index,string b,int bIndex)
{
//应该适用深度优先搜索匹配
//爆栈,直接给超时了
int len1 = a.length();
int len2 = b.length();
if (len1 == index)
{
if (len2 == bIndex)
{
return true;
}
return false;
}
if (len2 == bIndex)
{
if (len1 == index)
{
return true;
}
return false;
}

if (b[bIndex] == '?')
{
return traverse(a, index + 1, b, bIndex + 1);
}
else if (b[bIndex] == '*')
{
if (bIndex == (len2 - 1))
{
return true;
}
else
{
bool result = false;
for (int i = index; i < len1; i++)
{
result = traverse(a, i, b, bIndex + 1);
if (result)
return true;
}
return result;
}
}
else
{
bool result = false;
if (a[index] == b[bIndex])
{
result = traverse(a,index+1,b,bIndex+1);
return result;
}
else
{
return false;
}
}
}
};


后来看到网上说,这个不能用递归的,需要用迭代或者说动态规划的思想来做的。具体就是遇到"*"后,p字符在后面一个等着,s的指针可以任意后挪。
ex44 Wildcard Matching - HT - HT·生活
 

先贴一下我的代码,有比较详细的注释,下标版的

class Solution1 {
/*
* 根据网上迭代版本改的
*/
public:
bool isMatch(string s, string p)
{
int i, j;
int len1 = s.length();
int len2 = p.length();

bool star = false;
int tmpi=0, tmpj=0;
for (i = 0, j = 0; i < len1; i++, j++)
{
switch (p[j])
{
case '?': break; //?能够匹配任何字符
case '*':
star = true; //忽略 *号
tmpi = i;
tmpj = j;
do
{
tmpj++;//跳过重复的 *号
} while (p[tmpj]=='*');
if (j == len2 )
return true; //如果后面没有字符了的话,直接全部匹配
i = tmpi - 1; //记录上个时刻的位置,也就是,下一刻开始迭代的位置
j = tmpj - 1; //这里减掉1是为了抵消后面一次循环的自增1
break;
default:
if (s[i] != p[j])
{
if (!star)
return false; //前面如果没有*号的话直接就退出了
tmpi++;
i = tmpi - 1; //这里减掉1是为了抵消上面一次循环的自增1
j = tmpj - 1;
}
break;
}
}
while (p[j] == '*')
j++;
if (j == len2)
return true; //如果后面灭有字符了的话,直接全部匹配
else
{
return false;
}
}
};


再看看别人的递归版本,如此精简

// LeetCode, Wildcard Matching
// 递归版,会超时,用于帮助理解题意
// 时间复杂度O(n!*m!),空间复杂度O(n)
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '*') {
while (*p == '*') ++p; //skip continuous '*'
if (*p == '\0') return true;
while (*s != '\0' && !isMatch(s, p)) ++s;

return *s != '\0';
}
else if (*p == '\0' || *s == '\0') return *p == *s;
else if (*p == *s || *p == '?') return isMatch(++s, ++p);
else return false;
}
};


然后迭代版本也是很简单的思路,我的下标版本就是在这个上面改动的。

// LeetCode, Wildcard Matching
// 迭代版,时间复杂度O(n*m),空间复杂度O(1)
class Solution {
public:
bool isMatch(const char *s, const char *p) {
bool star = false;
const char *str, *ptr;
for (str = s, ptr = p; *str != '\0'; str++, ptr++) {
switch (*ptr) {
case '?':
break;
case '*':
star = true;
s = str, p = ptr;
while (*p == '*') p++; //skip continuous '*'
if (*p == '\0') return true;
str = s - 1;
ptr = p - 1;
break;
default:
if (*str != *ptr) {
// 如果前面没有'*',则匹配不成功
if (!star) return false;
s++;
str = s - 1;
ptr = p - 1;
}
}
}
while (*ptr == '*') ptr++;
return (*ptr == '\0');
}
};


看来关于字符串的处理还是要好好学习。

参考
http://www.acmerblog.com/leetcode-solution-wildcard-matching-6318.html
http://blog.csdn.net/tingmei/article/details/8049926
  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017