剑指offer：正则表达式匹配
剑指offer：正则表达式匹配
题意描述
请实现⼀个函数⽤来匹配包括'.'和''的正则表达式。模式中的字符'.'表⽰任意⼀个字符，⽽''表⽰它前⾯的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab ac a"匹配，但是
与"aa.a"和"ab*a"均不匹配
解题思路
⼀、思路⼀
1. 两个字符串都为空，返回true
2. 当第⼀个字符串不空，⽽第⼆个字符串空了，返回false（因为这样，就⽆法匹配成功了,⽽如果第⼀个字符串空了，第⼆个字符串⾮
空，还是可能匹配成功的，⽐如第⼆个字符串是“a a a a”，由于‘ * ’之前的元素可以出现0次，所以有可能匹配成功）
3. 开始匹配第⼀个字符，这⾥有两种可能：匹配成功或匹配失败。但考虑到pattern下⼀个字符可能是‘ * ’，这⾥我们分两种情况讨论：
pattern下⼀个字符为‘ * ’或不为‘ * ’：
pattern下⼀个字符不为‘ * ’：
如果str第⼀个字符和ptr中的第⼀个字符相匹配，那么str和ptr都后移⼀个字符，然后匹配剩余的。
如果str第⼀个字符和ptr中的第⼀个字符相不匹配，直接返回false。
pattern下⼀个字符为‘ * ’时，稍微复杂⼀些，因为‘ * ’可以代表0个或多个。这⾥把这些情况都考虑到：
x* 匹配0个字符，str不变，ptr后移两位，跳过这个’ * ‘
x* 匹配1个字符时，str+1，ptr+2，匹配str下个字符，并且跳过’ * ‘
x* 匹配多个字符时，str+1，ptr不变，继续匹配str下个字符
匹配⼀个也可以看成匹配多个
public class Solution {
public boolean match(char[] str, char[] pattern){
if(str == null && pattern == null) return true; //str、pattern都为空，返回true
if(str != null && pattern == null) return false;//str不为空，pattern为空，匹配失败
return matchCore(str,0,pattern,0);
}
public boolean matchCore(char[] str, int s1, char[] ptr, int p1) {
//str匹配到尾部，ptr匹配到尾部，匹配成功
if(s1 == str.length && p1 == ptr.length){
return true;
}
/
/str没有匹配到尾部，ptr匹配到尾部，匹配失败
if(s1 != str.length && p1 == ptr.length){
return false;
}
//p1的下⼀个字符为‘*’，并且没有越界
if(p1+1<ptr.length && ptr[p1 + 1] == '*'){
//如果s1没有匹配到尾部，p1 == s1 或者p1 = ‘。’
if((s1 != str.length && ptr[p1] == str[s1]) ||(ptr[p1] == '.' && s1 != str.length)){
return matchCore(str,s1,ptr,p1+2) || //X*匹配0个字符
//matchCore(str,s1+1,ptr,p1+2)|| //X*匹配1个字符
matchCore(str,s1+1,ptr,p1);  //X*匹配多个字符，继续匹配s1下个字符
}else{
//s1 ！= p1 并且 p1 ！= ‘。’，匹配不成功，跳过‘ * ’
return matchCore(str,s1,ptr,p1 + 2);
}
}
//str没有匹配到尾部，p1 == s1 或者 p1 = ‘。’，但p1下⼀位不是‘*’
if((s1 != str.length && ptr[p1] == str[s1])||(ptr[p1] == '.' && s1 != str.length)){
//匹配s1下⼀位与p1下⼀位
return matchCore(str,s1 + 1,ptr,p1 + 1);
}
return false;
}
}
⼆、思路⼆
1. 使⽤动态规划，DP分为正向与反向，这⾥使⽤那种呢？
2. 根据前⾯matchCore(str,s1 + 1,ptr,p1 + 1)，相当于dp[ i ] [ j ] = dp[ i + 1 ] [ j + 1 ]，所以我么采⽤反向
3. 初始化boolean dp[ len1 + 1 ] [ len2 + 1 ]，其中len1=str.length,len2=pattern.length
4. 初始化dp[ len1 ] [ len2 ] = true，含义是从两个字符串的末位开始匹配，“”与“”⼀定为true
5. 循环
外循环：因为我们要⽤aa*匹配aaa，以aaa为外循环，注意，从""开始匹配接下来a,aa,aaa
内循环：拿aa* 匹配：匹配顺序 * ，a* ，aa*
public class Solution {
public boolean match(char[] str, char[] pattern){正则匹配第二个符合的
if(str == null || pattern == null) return true;
boolean[][] dp = new boolean[str.length+1][pattern.length+1];
dp[str.length][pattern.length] = true; //末尾“”与“”⼀定匹配
for(int i=str.length;i>=0;i--){ //从空串开始匹配
for(int j=pattern.length-1;j>=0;j--){//从最后⼀个字符开始匹配
if(j+1<pattern.length && pattern[j+1] == '*'){ //下⼀位是*，并且没有越界                        //str = ptr 或者 ptr+1 = 。
if(i < str.length && (str[i] == pattern[j] || pattern[j] == '.')){
dp[i][j] = dp[i][j+2] || dp[i + 1][j]; //匹配0个、1个或多个
}else{
dp[i][j] = dp[i][j+2]; //跳过*
}
}else{
//下⼀位不是*，并且str = ptr || ptr+1 = 。
if(i != str.length &&(str[i] == pattern[j] || pattern[j] == '.')){
dp[i][j] = dp[i+1][j+1]; //匹配下⼀位
}
}
}
}
return dp[0][0];
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。