首页 > 试题广场 >

正则表达式匹配

[编程题]正则表达式匹配
  • 热度指数:90543 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
1.模式中的字符'.'表示任意一个字符
2.模式中的字符'*'表示它前面的字符可以出现任意次(包含0次)。
在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配

数据范围:
1.str 只包含从 a-z 的小写字母。
2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *,无连续的 '*'。
3.
4.


示例1

输入

"aaa","a*a"

输出

true

说明

中间的*可以出现任意次的a,所以可以出现1次a,能匹配上              
示例2

输入

"aad","c*a*d"

输出

true

说明

因为这里 c 为 0 个,a被重复一次, * 表示零个或多个a。因此可以匹配字符串 "aad"。              
示例3

输入

"a",".*"

输出

true

说明

".*" 表示可匹配零个或多个('*')任意字符('.')              
示例4

输入

"aaab","a*a*a*c"

输出

false
开始不明白,后来发现这就是一个背包问题参考https://www.bilibili.com/video/BV1th411o7Rg/
https://www.bilibili.com/video/BV1UY4y1f7Ya/

这里我先初始化dp[0][0],因为空字符匹配空的正则表达式为true,
然后再初始化第一行和第一列,在定义dp[][]的时候我们已经初始化所有的为false,因为空的正则表达式匹配A,AA,AAAB...都为false所以第一列剩余部分都是false所以我们只需要初始化第一行就行了。
初始化第一行的判定条件很简单,只需要在找到*的时候往前回退两格,如果那个格子上为true,就填true,其他都为false,推理也很简单,空字符匹配空正则,空字符匹配A*,空字符匹配A*B*,但是A*CB*,A*.B*就不匹配了。
剩下就是中间部分了


首先是如果遇到*,先看前两个格子的是否为true和上面同理,如果结果是false再看当前的pattern字符和str字符是否匹配,再看上一个str是否匹配,例如字符A匹配正则A*,字符也AA匹配正则A*,所以在字符添加了一个A后我们要看这个添加的A和正则的A*中的A是否匹配,匹配了并且前一个字符A和正则A*也是匹配的那说明现在字符AA和正则A*也是匹配的。
但还有一种情况容易被忽略就是字符A和正则.*也是匹配的,添加一个A,AA和.*也是匹配的。所以这里不能单纯的匹配字符A和正则A,还要匹配字符A和正则. 所以我在原来的代码上加上了判断.的条件
//原来的代码 
pattern.charAt(j-2)==str.charAt(i-1)&&dp[i-1][j]==true
//增加了.的判断
 (pattern.charAt(j-2)==str.charAt(i-1)||pattern.charAt(j-2)=='.')&&dp[i-1][j]==true

*解决了后面就只剩下字母和.了。
.的处理方式其实和字母的处理方式差不多,例如字符AAAB匹配正则A*B,当我们想知道字符AAABC是否匹配正则A*B.时,就看.和C是否匹配,如果匹配,再看字符AAAB和正则A*B是否匹配,这两个条件都符合那就说明它们是匹配的,字母也是同理,只需要看一下字符的字母和正则的字母是否匹配即可。
最后二维数组dp[][]右下角的最后一个格子就是我们要求得答案。
语言的表达能力有限,推荐大家画一画,画一画就什么都懂了
代码如下
public class Solution {
    public boolean match(String str, String pattern) {
        boolean[][] dp = new boolean[str.length()+1][pattern.length()+1];
        dp[0][0] = true;
        //初始化第一行
        for (int col = 1;col<dp[0].length;col++) {
            if (pattern.charAt(col-1)=='*'&&dp[0][col-2]==true) {
                dp[0][col] = true;
            }
        }
        //中间部分
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if((pattern.charAt(j-1)==str.charAt(i-1)&&dp[i-1][j-1]==true)||(pattern.charAt(j-1)=='.'&&dp[i-1][j-1]==true)){
                    dp[i][j] = true;
                }
                if((pattern.charAt(j-1)=='*'&&dp[i][j-2]==true)||(pattern.charAt(j-1)=='*'&&(pattern.charAt(j-2)==str.charAt(i-1)||pattern.charAt(j-2)=='.')&&dp[i-1][j]==true)){
                    dp[i][j] = true;
                }
            }
        }
        return dp[str.length()][pattern.length()];
    }
}


发表于 2024-01-14 14:51:03 回复(0)
一把过,自己多写点测试用例就行了。我还处理了 .*的用例,我把它当做一个可以是0个点到n个点的情况处理。字符*这种处理需要从零开始尝试遍历。
发表于 2023-12-15 13:23:16 回复(0)
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        // 使用动态规划的算法来解决
        int m = str.length();
        int n = pattern.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        // 默认是false,所以只需要判断第一行就行
        for(int i = 1;i <= n;i++){
            if(pattern.charAt(i-1) == '.' && i == 1){
                dp[0][i] = true;
            }else if(pattern.charAt(i-1) == '*'){
                dp[0][i] = dp[0][i-2];
            }
        }
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if(str.charAt(i-1) == pattern.charAt(j-1) || pattern.charAt(j-1) == '.')
                    dp[i][j] = dp[i-1][j-1];
                else{
                    // 1. 首先*的左左为真即为真! 2. 其次上为真,并且字符串pattern中*的左边等于当前str中的字符串(或者.)才能为真!
                    if((j>=2) && (dp[i][j-2] == true || (dp[i-1][j] == true && (str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j-2) == '.')))){
                        dp[i][j] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }
}
发表于 2023-09-04 16:44:06 回复(0)
public boolean match (String str, String pattern) {
    boolean[][] dp = new boolean[str.length() + 1][pattern.length() + 1];
    dp[0][0] = true;
    // 初始化
    for(int j=1;j<pattern.length()+1;j++)
    {
        if(pattern.charAt(j-1) == '*')
            dp[0][j] = dp[0][j-2];
    }
    for (int i = 1; i < str.length() + 1; i++) {
        for (int j = 1; j < pattern.length() + 1; j++) {
            // 如果i、j字符相同
            // 如果j是'.',即可以是任意字符 aba ab.
            if (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')
                dp[i][j] = dp[i - 1][j - 1];
            else {
                // 如果j是字母 aba abb
                if (pattern.charAt(j - 1) >= 'a' && pattern.charAt(j - 1) <= 'z')
                    dp[i][j] = false;
                // 如果j是'*',可以重复前面任意次 abbbb a.*
                else if (pattern.charAt(j - 1) == '*') {
                    int m = i;
                    dp[i][j] = dp[m][j - 2];
                    while (m >= 1 && (str.charAt(m - 1) == pattern.charAt(j - 2) ||
                                      pattern.charAt(j - 2) == '.')) {
                        // 去掉所有和*前面字符相同的字符
                        m = m - 1;
                        dp[i][j] = dp[i][j] || dp[m][j - 2];
                    }
                }
            }
        }
    }
    return dp[str.length()][pattern.length()];
}

发表于 2023-03-12 16:28:23 回复(0)
import java.util.*;


public class Solution {
    public boolean match (String str, String pattern) {
        // write code here
        int n = str.length(), m = pattern.length();
        boolean[][] dp = new boolean[n + 1][m +
                                            1]; //表示前m个字符和前n个正则是否匹配
        dp[0][0] = true;
        //""和".*" 匹配
        for (int i = 0; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (pattern.charAt(j - 1) == '*' && j >= 2) {
                    dp[i][j] = dp[i][j - 2];//* 匹配 0 次 对应状态方程f(i,j) = f(i,j - 2)
                    if (isMatch(str, pattern, i, j - 1)) { //匹配至少一次 * 前面的
                        dp[i][j] = dp[i][j] ||
                                   dp[i - 1][j]; // 对应状态方程f(i,j) = f(i,j - 2) || f(i - 1, j)
                    }
                } else {
                    if (isMatch(str, pattern, i, j)) { //匹配 . 或者相同字符 f(i,j) = f(i - 1,j - 1)
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[n][m];
    }

    public boolean isMatch(String s, String p, int i, int j) {
        if (i == 0 || j == 0) return false;
        return s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.';
    }
}

发表于 2023-01-26 14:25:36 回复(0)
这个状态转移方程太恶心了,配了半天
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        boolean[][] dp = new boolean[str.length() + 1][pattern.length() + 1];
        dp[0][0] = true;
        int l = 0;
        for (int j = 1; j < pattern.length() + 1; j++) {
            if (l == 1 && pattern.charAt(j - 1) == '*') {
                dp[0][j] = true;
                l--;
                continue;
            }
            dp[0][j] = false;
            l++;
        }
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < pattern.length(); j++) {
                if ((str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.') &&
                        dp[i][j]) {
                    dp[i + 1][j + 1] = true;
                    continue;
                }
                if (pattern.charAt(j) == '*') {
                    dp[i + 1][j + 1] = dp[i][j + 1] && (str.charAt(i) == pattern.charAt(j - 1) ||
                                                        pattern.charAt(j - 1) == '.');
                    if (!dp[i + 1][j + 1]) {

                        dp[i + 1][j + 1] = j > 0 && dp[i+1][j - 1];
                    }
                }
            }
        }
        return dp[str.length()][pattern.length()];
    }
}



发表于 2022-11-12 15:29:25 回复(0)
java方法
这个题有两个符号,也就有两种递推方式:
第一种是“。”,当规则串走到“。”的时候,由于是通配符,dp【i】【j】 = dp【i-1】【j-1】,之前的串相等当前也相等。
第二种是“*”这种就比较麻烦,当当规则串走到“*”的时候,需要找到*前面一位的字符假设为 a ,可能出现0 次,1次,2次。。。首先处理0次的情况,这时dp【i】【j】 = dp【i】【j-2】,如果这个串出现0次的情况与匹配串匹配上了,后面就不需要判断了。如果没匹配上,就要判断出现1次即 dp【i-1】【j】(两个串 一个是 aaa ,一个是 aa*,可以从  aa 与aa*递推出来,进而可以从 a 与 aa* ,递推出来, 当走到 a 与 aa*, 可以从 “” 与 aa* ||  a与 a递推)
个人解法,不知道是复杂度怎么样
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        //init
        boolean[][] dp = new boolean[str.length() + 1][pattern.length()+1];
        for (int i = 0; i < str.length() + 1; i++) {
            for (int j = 0; j < pattern.length() + 1; j++) {
                if(i==0 &&j==0) dp[i][j] = true;
                if (i == 0 && j>1 && pattern.charAt(j-1) == '*') dp[i][j] = dp[i][j - 2];
            }
        }
        //for for
        for (int i = 1; i < str.length() + 1; i++) {
            for (int j = 1; j < pattern.length() + 1; j++) {
                if(str.charAt(i-1) == pattern.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else if(pattern.charAt(j-1) == '.') dp[i][j] = dp[i-1][j-1];
                else if(pattern.charAt(j-1) == '*' ){
                    dp[i][j] = dp[i][j-2];
                    if(str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j-2)=='.'){
                        dp[i][j] = dp[i][j] ||  dp[i-1][j];
                    } 
                }

                        
            }
        }
        return dp[str.length()][pattern.length()];
    }
}


发表于 2022-09-22 14:06:58 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        //define
        boolean[][] dp=new boolean[str.length()+1][pattern.length()+1];
        //initialize
        dp[0][0]=true;
        for(int i=1;i<=str.length();i++){
            dp[i][0]=false;
        }
        for(int j=1;j<=pattern.length();j++){
            char c=pattern.charAt(j-1);//长度为j,拿的是index=j-1的字符
            if(c!='*'){dp[0][j]=false;}
            else{
                dp[0][j]=dp[0][j-2];
            }
        }
        //开始状态转移
        for(int i=1;i<=str.length();i++){
            for(int j=1;j<=pattern.length();j++){
                char c1=str.charAt(i-1),c2=pattern.charAt(j-1);
                if(c2=='*'){
                    char c3=pattern.charAt(j-2);
                    if(c3!='.'&&c3!=c1){dp[i][j]=dp[i][j-2];}
                    else{
                        dp[i][j]=dp[i][j-2]||dp[i-1][j];
                    }
                }
                else if(c2=='.'){
                    dp[i][j]=dp[i-1][j-1];
                }
                else{//字母比较
                    if(c1!=c2){dp[i][j]=false;}
                    else{dp[i][j]=dp[i-1][j-1];}
                }
            }
        }
        //return
        return dp[str.length()][pattern.length()];
        
    }
}

发表于 2022-08-11 22:02:06 回复(0)
    public boolean match (String str, String pattern) {
        int m = str.length();
        int n = pattern.length();
        // 因为最后返回dp[m][n] 表示前m个字符和前n个正则是否匹配 mn可以看作字符串长度或字符个数
        // 所以数组大小必须是m+1 和 n + 1才会有m和n的索引
        boolean[][] dp = new boolean[m + 1][n + 1];
        // base case 空串空正则
        dp[0][0] = true;
        // 注意是小于等于 因为最后输出dp[m][n]
        for(int i = 0; i <= m; i++){
            for (int j = 0; j <= n; j++){
                // 递归计算所有字串和子正则是否匹配
                // 正则为空 除了字符串为空都不匹配
                // 但是字符串为空 正则不为空也是需要通过计算得到的
                if(j == 0)  dp[i][j] = (i == 0 ? true:false);
                // 不为 *
                else{
                    // j一定大于0
                    if(pattern.charAt(j - 1) != '*'){
                        if( i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.'))
                            dp[i][j] = dp[i - 1][j - 1];
                        // 如果i<0 那么就是空字符串和结尾不为*的正则进行匹配那么一定为false 这是空串有正则的一种情况
                        // 如果i>0 但是字符串末尾字符与正则末尾字符不相同且其不为'.' 都是默认值false
                    }else {
                        // 为 * 不管i为什么情况 都可以出现0次
                        // 如果用例正常不会出现j<2的情况
                        if(j >= 2) dp[i][j] |= dp[i][j - 2];
                        if(i > 0 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.'))
                            dp[i][j] |= dp[i - 1][j];
                        // 如果i == 0 走 dp[i][j] |= dp[i][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }

发表于 2022-05-03 10:36:03 回复(0)
import java.util.*;
public class Solution {

    public boolean match (String str, String pattern) {
        // write code here
        int len1 = str.length();
        int len2 = pattern.length();
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        // 下面是为了初始化x*x*x*x*这种情况
        for(int j = 2; j <= len2; j++){
            if(pattern.charAt(j - 1) == '*'){
                dp[0][j] = dp[0][j - 2];
            }
        }
        // i和j表示长度
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(pattern.charAt(j - 1) != '*'){
                    if(isMatch(str.charAt(i - 1), pattern.charAt(j - 1))){
                        dp[i][j] = dp[i - 1][j - 1];
                    }else{
                        dp[i][j] = false;
                    }
                }else{
                    // 判断pattern '*'之前的字符是否和str当前字符匹配
                    if(isMatch(str.charAt(i - 1), pattern.charAt(j - 2))){
                        //‘*’之前的字符取0次 || ‘*’之前的字符取多次
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }else{
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[len1][len2];
    }

    // 判断当前两个字符是否匹配
    private boolean isMatch(char ch1, char ch2){
        if(ch1 == ch2 || ch2 == '.'){
            return true;
        }
        return false;
    }
}
发表于 2022-04-08 17:12:21 回复(0)
使用str.substring来做,str.substring(str.length())会返回""(空字符串)。如果传入的大于length才会抛异常。

1.当pattern匹配完时,看str是否匹配完,匹配完就成功否则失败。
2.先匹配单个字符或者pattern字符为'.'的情况,结果给boolean singleMatch
3.如果pattern.charAt(1)=='*',那么分为匹配0个或匹配多个。匹配多个时需要带上singleMatch结果才行。
4.如果没有'*',则pattern和str都往后继续匹配。

里面注意加上XXX.length()>0或1的判断,因为后面需要取,就提前判断下。

public class Solution {
    //巧用substring,当substring(str.length())时,得到""。若substring大于length,则抛异常。
    public boolean match (String str, String pattern) {
        //当pattern匹配完,看str匹配完了没。str匹配完了,就成功否则失败
        if(pattern.length() == 0){
            return str.length() == 0;
        }
        //一个一个匹配,和'.'的情况
        boolean singleMatch = str.length() > 0 && 
            (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.');
        //pattern有'*'的情况
        if(pattern.length() > 1 && pattern.charAt(1) == '*'){
            //匹配0个或多个
            return match(str, pattern.substring(2)) || 
                (singleMatch && match(str.substring(1), pattern));
        }else{
            //pattern没有'*'的情况
            return singleMatch && match(str.substring(1), pattern.substring(1));
        }
    }
}


发表于 2022-04-03 14:45:27 回复(1)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match(String str, String pattern) {
        // write code here
        int len1 = str.length();
        int len2 = pattern.length();

        str = " " + str;
        pattern = " " + pattern;

        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        for (int i = 0; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (j + 1 <= len2 && pattern.charAt(j + 1) == '*') {
                    continue;
                }
                if (pattern.charAt(j) != '*') {
                    dp[i][j] = i >= 1 && j >= 1 && dp[i - 1][j - 1] && (pattern.charAt(j) == '.' ||
                            str.charAt(i) == pattern.charAt(j));
                } else {
                    dp[i][j] = (j >= 2 && dp[i][j - 2]) || (i >= 1 && j >= 1 && dp[i - 1][j] &&
                            (str.charAt(i) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.'));
                }
            }
        }
        return dp[len1][len2];
    }
}
发表于 2022-03-23 17:31:15 回复(0)
public boolean match (String str, String pattern) {
        // write code here
        // 递归实现正则表达式匹配
        return match(str.toCharArray(), 0, pattern.toCharArray(), 0);
    }
    public boolean match(char[] str, int si, char[] pattern, int pi){
        // 递归结束条件是:如果pattern走完了,chars还没匹配结束,则说明无法匹配成功
        if (pi >= pattern.length){
            return si >= str.length;
        }
        // 如果pattern[pi + 1] =“*”
        if (pi + 1 < pattern.length && pattern[pi + 1] == '*'){
            if (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')){
                boolean ret2 = match(str, si, pattern, pi + 2); // str[si]匹配pattern,匹配到0个字符,那么pi需要向右移动两位
                boolean ret1 = match(str, si + 1, pattern, pi + 2); // str[si]的值与pattern[pi]匹配一次,那么si需要向右移动一位,pi向右移动两位
                boolean ret3 = match(str, si + 1, pattern, pi); // str[si]的值匹配了一个,再匹配下一个,那么pi不动,si需要向右移动一位
                return ret1 || ret2 || ret3 ;
            }else {
                // *前面的值匹配失败,那么si不动,pi需要向右移动两位
                return match(str, si, pattern, pi + 2);
            }
        }
        // 如果str[si]的值和pattern[pi]的值相等或者pattern[pi] =“.”,那么匹配成功,si和pi都向右移动一位
        if (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')){
            return match(str, si + 1, pattern, pi + 1);
        }
        return false;
    }

发表于 2022-03-17 18:11:29 回复(0)
再您妈的见
import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
        // write code here
        return str.matches(pattern);
    }
}


发表于 2022-01-23 18:43:37 回复(4)
/**
     * str     pattern
     * 1.   null    null
     * 2.   null    !null   .*
     * 3.   !null   null
     * 4.   !null   !null
     *     1)  . | char    true
     *     2)  .*
     *         a)  取   j不动,i往前走
     *         b)  不取  i不动,j-=2
     */
    public boolean match(String str, String pattern) {
        int n = str.length();
        int m = pattern.length();
        boolean[][] dp = new boolean[n + 1][m + 1];

        dp[0][0] = true;
        for (int i = 2; i <= m; i += 2) {
            if (pattern.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = false;
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (pattern.charAt(j - 1) == '*') {
                    if (match(str.charAt(i - 1), pattern.charAt(j - 2))) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && match(str.charAt(i - 1), pattern.charAt(j - 1));
                }
            }
        }
        return dp[n][m];
    }


    private boolean match(char target, char source) {
        return source == '.' || source == target;
    }

发表于 2021-12-30 17:27:24 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    /*
    public boolean match (String str, String pattern) {
        // write code here
        if (pattern.equals("")) {
            if (str.equals(""))
                return true;
            else
                return false;
        }
        boolean res = isMatch(str, str.length()-1, pattern, pattern.length()-1);
        return res;
    }
    
    public boolean isMatch(String str, int i, String pattern, int j) {
        //表示pattern走到头了
        if (j < 0) {
            //原字符串若也到头了,true
            if (ipa < 0)
                return true;
            else
                return false;
        }
        //若当前需要匹配的不是‘*’,则它要么是'.'要么是字符,且必须保证 i>=0, 即原str中还有可用来匹配的字符
        if (pattern.charAt(j) != '*') {
            if (i >= 0 && (pattern.charAt(j) == '.' || pattern.charAt(j) == str.charAt(i)))
                //接着看前面的是否匹配
                return isMatch(str, i-1, pattern, j-1);
            else
                return false;
        }
        //若当前需要匹配的是“*”,则有两种可能,即"*"前面的字符根本用不上,与“*”前面的字符用上了好几次
        else {
            //用不上当前“*”前字符时,直接抛弃pattern当下与前一位,接着匹配余下字符
            boolean no = isMatch(str, i, pattern, j-2);
            //接下来看若需要用“*”与之前字符时
            boolean yes = false;
            //首先要保证str还有可用来匹配的字符,其次看是否满足可匹配的条件
            if (i >= 0 && (str.charAt(i) == pattern.charAt(j-1) || pattern.charAt(j-1) == '.'))
                yes = isMatch(str, i-1, pattern, j);
            //哪条路走得通,都可以
            return yes || no;
        }
    }*/
    
    //动态规划
    public boolean match (String str, String pattern) {
        if (pattern.equals("")) {
            if (str.equals(""))
                return true;
            else
                return false;
        }
        int m = str.length();
        int n = pattern.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pattern.charAt(j-1) != '*') {
                    if (i > 0 && (pattern.charAt(j-1) == '.' || pattern.charAt(j-1) == str.charAt(i-1)))
                        //接着看前面的是否匹配
                        dp[i][j] = dp[i-1][j-1];
                }
                else {
                    boolean tmp1 = false;
                    boolean tmp2 = false;
                    if (j >= 2) {
                        tmp1 = dp[i][j-2];
                        if (i > 0 && (str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j-2) == '.'))
                            tmp2 = dp[i-1][j];
                    }
                    dp[i][j] = tmp1 || tmp2;
                }
            }
        }
        return dp[m][n];
    }
}

发表于 2021-12-29 23:23:59 回复(0)