LeetCode - Regular Expression Matching And Wildcard Matching

最近刷LeetCode遇到关于正则匹配的编程题,在这里记录下解题思路。

Regular Expression Matching

Link

Regular Expression Matching - LeetCode

Description

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
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

Recursive Solution

Discusss

当模式中的第二个字符不是“*”时:

  1. 如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。
  2. 如果字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。

而当模式中的第二个字符是“*”时:

  1. 如果字符串第一个字符跟模式第一个字符不匹配,则模式后移2个字符,继续匹配。
  2. 如果字符串第一个字符跟模式第一个字符匹配,可以有2种匹配方式:
    1. 模式后移2字符,相当于x*被忽略;
    2. 字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位;

Code

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.equals("") && p.equals("")) return true;
        if (!s.equals("") && p.equals("")) return false;
        if (p.length() > 1 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) ||
                    (s.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)) && isMatch(s.substring(1), p));
        }
        if (s.length() != 0 && p.length() != 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0)))
            return isMatch(s.substring(1), p.substring(1));
        return false;
    }
}

Dynamic Planning Solution

Discusss

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-2]    // in this case, a* counts as empty

Code

public class Solution {
    public boolean isMatch(String s, String p) {
        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][j+1] || dp[i+1][j-1]);
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

Wildcard Matching

Link

Wildcard Matching - LeetCode

Description

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "*") ? true
isMatch("aa", "a*") ? true
isMatch("ab", "?*") ? true
isMatch("aab", "c*a*b") ? false

Recursive Solution

Discuss

当模式中的第一个字符不是“*”时:

  1. 如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。
  2. 如果字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。

而当模式中的第一个字符是“*”时:

  1. 模式后移1字符,相当于*被忽略;
  2. 字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位;

Code

@Deprecated
//(TimeLimitExceededException)
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.length() == 0 && p.length() == 0) return true;
        if (s.length() != 0 && p.length() == 0) return false;
        if (s.length() > 0 && (p.charAt(0) == '?' || s.charAt(0) == p.charAt(0))) return isMatch(s.substring(1), p.substring(1));
        if (p.charAt(0) == '*') return isMatch(s, p.substring(1)) || (s.length() > 0 && isMatch(s.substring(1), p));
        return false;
    }
}

Dynamic Planning Solution

Discuss

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:
          dp[i][j] = dp[i-1][j]    // in this case, * counts as multiple 
       or dp[i][j] = dp[i][j-1]    // in this case, * counts as empty

Code

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for (int j = 0; j < p.length(); j++)
            if (p.charAt(j) == '*' && dp[0][j]) dp[0][j+1] = true;
        for (int i = 0; i < s.length(); i++)
            for (int j = 0; j < p.length(); j++)
                if (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)) dp[i+1][j+1] = dp[i][j];
                else if (p.charAt(j) == '*') dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j];
        return dp[s.length()][p.length()];
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 135,010评论 19 139
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • error code(错误代码)=0是操作成功完成。error code(错误代码)=1是功能错误。error c...
    Heikki_阅读 3,457评论 1 9
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,951评论 2 36
  • 今天看到一段话,觉得甚为有理: “有人说,岁月是把杀猪刀,让迎风飞扬的少年,成了面目模糊的中年男人,让娇媚青春的少...
    八月茉莉阅读 1,984评论 2 3