[C++] Clean Code - 7 Lines DP - match[i][j] = isMatch(s.substr(i), p.substr(j))


  • 1

    DP Solution

    /**
     * if pattern runout - false
     * if string runout - pattern == "" or pattern == "a*b*c*"
     * 
     * Definitions:
     *      match[i][j] = isMatch(s.substr(i), p.substr(j));
     *      match[0][0] = isMatch(s, p);
     *      match[m][n] = isMatch("", ""); // m = s.size(), n = p.size();
     * 
     * Pattern:
     * match[i][j] =
     *               p[j+1] == '*' ? s[i] == p[j] && match[i+1][j]      // match("abc", "a*bc") if match("bc", "a*bc")
     *                                            || match[i][j + 2];   // match("bc", "a*bc") if match("bc", "bc")
     *               p[j] == '.' ? match[i+1][j+1]       // s[i] could be char, as long as match[i+1][j+1]
     *               p[j] == '\w' ? s[i] == p[j] && match[i+1][j+1];    // match("labc", "la*bc") if match("abc", "a*bc")
     * Expression:
     *  match[i][j] = j + 1 < n && p[j + 1] == '*'          // next char of pattern is '*'
     *      ? match[i][j + 2] || i < m && match[i + 1][j] && (p[j] == '.' || s[i] == p[j])
     *      : i < m && match[i + 1][j + 1] && p[j] != '*' && (p[j] == '.' || s[i] == p[j]);
    

    Code

    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.length(), n = p.length();
            vector<vector<bool>> match(m + 1, vector<bool>(n + 1, false));
            match[m][n] = true;
            for (int i = m; i >= 0; i--)
                for (int j = n - 1; j >= 0; j--)    // match[i != m][n] = false; no need to process
                    match[i][j] = j + 1 < n && p[j + 1] == '*' ? match[i][j + 2] || i < m && (p[j] == '.' || s[i] == p[j]) && match[i + 1][j] : i < m && (p[j] == '.' || s[i] == p[j]) && match[i + 1][j + 1];
            return match[0][0];
        }
    };
    

    A partially iterated example

     * s = "abcd"
     * p = "a.c*e*d"
     * 
     *     0 1 2 3 4 5 6 7 
     *     a . c * e * d 0  
     * 0 a               0  
     * 1 b               0  
     * 2 c               0  
     * 3 d               0  
     * 4     0 0 0 0 0 0 1
     * 
     *     0 1 2 3 4 5 6 7 
     *     a . c * e * d 0  
     * 0 a               0  
     * 1 b               0  
     * 2 c 0 1 1 0 0 0 0 0  
     * 3 d 0 0 1 0 1 0 1 0  
     * 4     0 0 0 0 0 0 1
     */
    

    Recursion

    class Solution {
    public:
        bool isMatch(string s, string p) {
            return match(s, p, 0, 0);
        }
        
        bool match(string s, string p, int s0, int p0) {
            if (s0 == s.length() && p0 == p.length()) {
                return true;
            }
            else if (s0 == s.length()) { // string runout, match only if pattern is like "a*b*c*d*"
                if ((p.length() - p0) % 2 == 1) {
                    return false;
                }
    
                for (int pi = p0; pi < p.length(); pi++) {
                    // if any even digit is not word char, or if any odd digit is not '*', cannot match
                    if ((pi - p0) % 2 == 0 ? (p[pi] == '*') : (p[pi] != '*')) {
                        return false;
                    }
                }
                return true;
            }
            else if (p0 == p.length()) { // pattern runout, can not match;
                return false;
            }
    
            if (p0 + 1 < p.length() && p[p0 + 1] == '*') {
                for (int si = s0; si < s.length() && (s[si] == p[p0] || p[p0] == '.'); si++) {
                    if (match(s, p, si + 1, p0 + 2)) {
                        return true;
                    }
                }
                return match(s, p, s0, p0 + 2);
            }
            else if (p[p0] == '.') {
                return match(s, p, s0 + 1, p0 + 1);
            }
            else {
                return s[s0] == p[p0] && match(s, p, s0 + 1, p0 + 1);
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.