Regular Expression/Wildcard Matching

Leave a comment

May 5, 2017 by oneOokay

  • Regular Expression Matching
  • Wildcard Matching

Regular Expression Matching:

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

dp和dfs backtracking:之不看答案写不出来系列

dp:首先确定了dp是一个二维的boolean数组. boolean[s.length() +1][p.length() + 1]: dp[i][j]表示: s到第i个char和p到第j个char是否match (难点在于当p.charAt(j) == ‘*’的时候是什么情况).

  1. 当p.charAt(j) == s.charAt(i)或者p.charAt(j) == ‘.’时: dp[i][j] = dp[i-1][j-1]
  2. 当p.charAt(j) == ‘*’:
    1. 把’a*’当成empty string:此时: dp[i][j] = dp[i][j – 2];
    2. 如果*之前的char match s(i):p.charAt(j-1) == s.charAt(i) || p.charAt(j-1) == ‘.’ : ‘a*’就可以是’a’,’aa’,’aaaa…’. 此时当前s(i)和p(j)最后一位一定是match的.那么dp[i][j]取决于:s(i-1)是否match p(j): dp[i][j] = dp[i-1][j].(还是不太好说明)…

特殊情况:s=”” 和 p=”a*” 是match的.所以需要初始化dp[0][i].

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        
        for (int i = 2; i <= n; i ++){
            if (p.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 (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.'){
                    dp[i][j] = dp[i - 1][j - 1];
                }else if (p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i][j - 2];
                    if (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.')
                        dp[i][j] |= dp [i - 1][j];
                }
            }
        }
        return dp[m][n];
    }

Wild card expression matching:

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
跟上面的区别在于: *跟它之前的char没有任何关系.
同样的boolean[][] dp.
  • 当s(i) == p(j)||p(j) == ?:dp[i][j] = dp[i-1][j-1]
  • 否则当p(j) == ‘*’时:
    • 首先’*’match empty string: dp[i][j] = dp[i][j-1]
    • ‘*’ match多个char: dp[i][j] = dp[i – 1][j]
    • 综上: dp[i][j] = dp[i][j – 1] || dp[i – 1][j]

http://www.cnblogs.com/yuzhangcmu/p/4116153.html

特殊情况: s=”aa” match “*”:需要初始化dp[0][i].

public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= n; i ++){
            if (p.charAt(i - 1) == '*')
                dp[0][i] = dp[0][i - 1];
        }
        
        for (int i = 1; i <= m; i ++){
            for (int j = 1; j <= n; j ++){
                if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[m][n];
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: