Wildcard Matching

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).

Example
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

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "?" and "*"
     * @return: A boolean
     */
    bool isMatch(const char *s, const char *p) {
        // write your code here
        if (!s || !p) {
            return true;
        }
        int slen = strlen(s);
        int plen = strlen(p);
        // pre processing
        // test if nostar character > lenth of s, we cannot match
        int nostar = 0;
        for (int pi = 0; pi < plen; ++pi) {
            if (p[pi] != '*') {
                nostar++;
            }
        }
        if (nostar > slen) {
            return false;
        }
        // dp
        vector<vector<bool>> dp(slen + 1, vector<bool>(plen + 1, false));
        dp[0][0] = true;
        // if has * matching any seq
        for (int i = 0; i < plen; ++i) {
            // dp[0][i+1] = dp[0][i] && p[i] == '*';
            if (p[i] != '*') {
                continue;
            }
            dp[0][i+1] = dp[0][i];   
        }
        // ordinary dp
        for (int si = 1; si < slen + 1; ++si) {
            for (int pi = 1; pi < plen + 1; ++pi) {
                // ?, copy the status from last string matching
                if (p[pi-1] == '?') {
                    dp[si][pi] = dp[si-1][pi-1];
                } else if (p[pi-1] == '*') {
                // *, copy the status from 
                // [si][pi-1], s[cur] to p[last], star matches s[cur]
                // [si-1][pi], s[last] to p[cur], star matches empty
                    dp[si][pi] = dp[si][pi-1] || dp[si-1][pi];
                } else {
                // letter matching one by one
                    dp[si][pi] = dp[si-1][pi-1] && s[si-1] == p[pi-1];
                }
            }
        }
        return dp[slen][plen];
    }
};

Similar problems

x

Tags

x