题解 | #正则表达式匹配#
正则表达式匹配
http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
动态规划 dp含义是以i-1结尾和j-1结尾的str能否用p去匹配。除了常规的动态规划之外，还要关注p中为*的情况，
当p中索引为j-1的元素为*时，考虑：j-2的元素与s[i-1]是否相等，不相等的话，那dp[i][j-1]肯定就是flase了，所以尽量去寻找dp[i][j-2],有true的希望，此时两个字符相当于空
j-2的元素与s[i-1]相等，只要满足一下任意一种都可以时true dp[i][j-1]为true，此时*相当于没有（保留j-2的元素），dp[i][j-2]为true，此时两个字符串为空，dp[i-1][j],此时相当于*表示为前面的那个元素和s[i-1]去匹配。最后返回的是dp[n][m].同时要注意dp数组的初始化。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
public boolean match (String str, String pattern) {
// write code herei
if(str==null||pattern==null){
return false;
}
int n=str.length();
int m=pattern.length();
char[]s=str.toCharArray();
char[]p=pattern.toCharArray();
boolean [][]dp=new boolean[n+1][m+1];
dp[0][0]=true;
for(int i=0;i<m;i++){ //当s长度为0的时候做初始化
if((p[i]=='*')&&(dp[0][i-1]==true)){ //跳过之前的那个元素所以要dp[0][i-1]
dp[0][i+1]=true;
}
}
//当p长度为0的时候，肯定都是false
for(int i=1;i<=n;i++){
char chS=s[i-1];
for(int j=1;j<=m;j++){
char chP=p[j-1];
if(chP=='.'||chP==chS){
dp[i][j]=dp[i-1][j-1];
}
else if(chP!=chS&&chP!='*'){
dp[i][j]=false;
}
else if(chP=='*'){
if(p[j-2]!=s[i-1]&&p[j-2]!='.'){
dp[i][j]=dp[i][j-2];
}
else{
dp[i][j]=dp[i][j-1]||dp[i][j-2]||dp[i-1][j];
}
}
}
}
return dp[n][m];
}
}
快手公司氛围 213人发布
投递快手等公司10个岗位 >