JZ19-题解 | #正则表达式匹配#
正则表达式匹配
http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
题目描述
请实现一个函数用来匹配包括'.'和'* '的正则表达式。模式中的字符'.'表示任意一个字符,而'* '表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab* ac* a"匹配,但是与"aa.a"和"ab* a"均不匹配.
算法思路:引自Maokt
每次从字符串里取出一个字符与模式中的字符匹配,如果模式中的字符是‘.’,它可以匹配字符串中的任意字符,如果不是,那么如果它与字符串中的字符相等则匹配。当字符串的字符和模式的字符匹配时,接着匹配后面的字符。
下面,考虑模式中的第二个字符是不是‘* ’。如果不是,则可以分为两种情况:
1、如果字符串中的第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的字符串和模式;
2、如果字符串中的第一个字符和模式中的第一个字符不匹配,则直接返回false。
当模式中的第二个字符是‘* ’时,又可以分为两种情况方式:
1、如果pattern中的第一个字符和str中的第一个字符不匹配,则将pattern后移两个字符,相当于忽略‘’和它前面的字符,因为‘’可以匹配字符串中的0个字符;
2、如果pattern中的第一个字符和str中的第一个字符匹配,则str后移一个字符,而在模式上又有两种选择:
2.1、pattern后移两个字符(例如字符串"ab"和模式"a* ab"匹配到str[0]和pattern[0]时,pattern后移两个字符,字符串后移一个字符)
2.2、pattern保持不变(例如字符串"aabbba"和模式"aab* a"匹配到str[2]和pattern[2]时,pattern保持不变,字符串后移一个字符)
代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool myMatch(string &s, string &p, int i, int j){
if(i<0&&j<0)
return true;
if(j<0)
return false;
//匹配一般字符
if(i>=0&&s[i]==p[j])
return myMatch(s, p, i-1, j-1);
//匹配.
if(i>=0&&p[j]=='.')
return myMatch(s, p, i-1, j-1);
//匹配*
if(p[j]=='*'){
//匹配0个字符
if(myMatch(s, p, i, j-2))
return true;
//匹配一个字符后递归调用
if(i>=0&&(p[j-1]=='.'||s[i]==p[j-1]))
if(myMatch(s, p, i-1, j))
return true;
}
return false;
}
bool match(string str, string pattern) {
// write code here
return myMatch(str, pattern, str.size()-1, pattern.size()-1);
}
};