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

HT·生活

123

 
 
 

日志

 
 

ex10 Regular Expression Matching  

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

  下载LOFTER 我的照片书  |
正则表达式的实现,太恶心了。

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
要注意“.*”这种特殊情况,我表示我自己写不出来,看的网上的代码。后面参考中第一个作者写的很好,我的几乎都是从那边借鉴过来。
ex10 Regular Expression Matching - HT - HT·生活
 这个题目要是不用递归估计真的会“死人”的,首先先看第二个字符是不是“*”号,如果是的话,就要进行扩展,如果不是的话,就正常匹配。开一个数组dp[i][j]表示的是s[i--len(s)] 是否和p[j-len(p)]匹配。
如果仔细分析的话,会有一个很明确的转移方程,
如果  p[j+1]!='*',则不扩展
if s[i]==p[j] || p[j]=='.' &&s!=NULL
dp[i][j] = dp[i+1][j+1]  //因为前面一个字符匹配了
else
//返回false
如果 p[j+1]=='*',则扩展
if s[i]==p[j] || p[j]=='.' &&s!=NULL
dp[i][j]就和 dp[i[[j+2]有关系了。
我上面的图中已经写了一些分析。如代码  
指针型的

bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function

if (0 == *p) return 0 == *s;

//判定p指向的第二个字符是否*号
if (*(p + 1) != '*')
{
if (*p == *s || (*p) == '.' && (*s) != 0)
{
return isMatch(s + 1, p + 1);
}
return false;
}
else
{
//p指向的第二个字符是*号
while (*p == *s || ((*p) == '.' && (*s) != 0))
{
//如果两个字符相等,或者p指向的是.号
if (isMatch(s, p + 2))
{
return true;
}
s++;
}
//如果不相等的话 直接把前面的去掉,因为有*号,所以前面的可以出现0次
return isMatch(s, p + 2);

}

}

下标型的

class Solution {
public:
bool isMatch(string s, string p)
{
bool result = traverse(s,0,p,0);
return result;
}
bool traverse(string s,int s_index,string p,int p_index)
{
if (p_index == p.length())
return s_index == s.length();
if (p[p_index + 1] != '*')
{
if (s[s_index] == p[p_index] || (p[p_index] == '.'&&s.length() != s_index))
{
return traverse(s, s_index+1,p, p_index+1);
}
return false;
}
else
{
while (s[s_index] == p[p_index] || (p[p_index] == '.' && s.length() != s_index))
{
//如果两个字符相等,或者p指向的是.号
if (traverse(s, s_index, p, p_index + 2))
{
return true;
}
s_index++;
}
//如果不相等的话 直接把前面的去掉,因为有*号,所以前面的可以出现0次
return traverse(s,s_index, p,p_index+2);
}
}
};



参考
http://blog.csdn.net/hopeztm/article/details/7992253
http://blog.csdn.net/doc_sgl/article/details/12719761
http://www.cnblogs.com/codingmylife/archive/2012/10/05/2712561.html
  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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