Wildcard Matching

Question:
http://www.lintcode.com/en/problem/wildcard-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).


Answer:

class Solution {
public:
    /*
     * @param s: A string 
     * @param p: A string includes "?" and "*"
     * @return: is Match?
     */
    bool isMatch(string &s, string &p) {
        if (p.empty())
            return false;
        int n = s.length();
        int m = p.length();
        bool f[n + 1][m + 1];
        memset(f, false, sizeof(f));
        f[0][0] = true;
        for (int i = 1; i <= n; i++)
            f[i][0] = false;
        for (int i = 1; i <= m; i++)
            f[0][i] = f[0][i - 1] && p[i - 1] == '*';
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1];
                } else if (p[j - 1] == '?') {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1]);
                }
            }
        } 
        return f[n][m];
    }
}; 

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️