首页 > 试题广场 >

正则表达式匹配

[编程题]正则表达式匹配

热度指数：9507 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请实现支持'.'and'*'.的通配符模式匹配

'.' 可以匹配任何单个字符。
'*' 可以匹配任何字符序列（包括空序列）。

匹配应该覆盖整个输入字符串（而不是部分）。 
函数声明为：
bool isMatch(const char *s, const char *p)

下面给出一些样例：
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

算法知识视频讲解

Java

Iosti

public class Solution {
    public boolean isMatch(String s, String p) {
        return s.replaceFirst(p,"Iosti").equals("Iosti");
    }
}

点开一看各位都在用动态规划惊了

编辑于 2019-01-28 19:59:34 回复(2)

Java

Holiday_12138

public class Solution {
    public boolean isMatch(String s, String p) {
        int n1=s.length();
        int n2=p.length();
        boolean[][] dp=new boolean[n1+1][n2+1];
        dp[0][0]=true;
        for(int i=1;i<n2&&p.charAt(i)=='*';i+=2){
            dp[0][i+1]=true;
        }
        for(int i=0;i<n1;i++){
            for(int j=0;j<n2;j++){
                if(p.charAt(j)=='.')
                    dp[i+1][j+1]=dp[i][j];
                else if(p.charAt(j)=='*'){
                    if(p.charAt(j-1)!=s.charAt(i) && p.charAt(j-1)!='.')
                        dp[i+1][j+1]=dp[i+1][j-1];
                    else
                        dp[i+1][j+1]=dp[i+1][j-1]||dp[i+1][j]||dp[i][j+1];
                }
                else
                    dp[i+1][j+1]=(dp[i][j]&&s.charAt(i)==p.charAt(j));
                        
            }
        }
        return dp[n1][n2];
    }
}

发表于 2017-05-31 17:13:05 回复(0)

Java

城市里的养猫者

This Solution use 2D DP. beat 90% solutions, very simple.

Here are some conditions to figure out, then the logic can be very straightforward.

1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:  1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty  2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':  dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a   or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a  or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty

Here is the solution

public boolean isMatch(String s, String p) {

    if (s == null || p == null) {
        return false;
    }
    boolean[][] dp = new boolean[s.length()+1][p.length()+1];
    dp[0][0] = true;
    for (int i = 0; i < p.length(); i++) {
        if (p.charAt(i) == '*' && dp[0][i-1]) {
            dp[0][i+1] = true;
        }
    }
    for (int i = 0 ; i < s.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == '.') {
                dp[i+1][j+1] = dp[i][j];
            }
            if (p.charAt(j) == s.charAt(i)) {
                dp[i+1][j+1] = dp[i][j];
            }
            if (p.charAt(j) == '*') {
                if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                    dp[i+1][j+1] = dp[i+1][j-1];
                } else {
                    dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}