Python DP solution


  • 9
    C

    For a 2d table, dp[i][j] would mean whether sub-pattern p[:i + 1] matches sub-string s[:j + 1].
    Most tricky part is when the current pattern letter is *, suppose its index is i, p[:i + 1] will match sub-string s[:j + 1] if p[:i + 1] matches s[:j] or p[:i] matches s[:j + 1], namely current cell value is true if its top or its left is true. Since the current row only depends on the previous row, we can use two rolling lists to do the dp instead of a matrix.

    def isMatch(self, s, p):
        l = len(s)
        if len(p) - p.count('*') > l:
            return False
        dp = [True]  + [False] * l
        for letter in p:
            new_dp = [dp[0] and letter == '*']
            if letter == '*':
                for j in range(l):
                    new_dp.append(new_dp[-1] or dp[j + 1])
            elif letter == '?':
                new_dp += dp[:l]
            else:
                new_dp += [dp[j] and s[j] == letter for j in range(l)]
            dp = new_dp
        return dp[-1]

  • 0
    G

    Excellent! I was trying a backtracking solution but I think recursive strategies fail due to memory limits/stack overflows.


  • 0
    C

    Thanks! Recursion without memoization will cause TLE/MLE due to duplicate calls, with memoization it probably will not TLE, but may still MLE.


  • 0
    J

    Good idea. Here is my C++ version:

    class Solution {
    public:
        bool isMatch(const char* s, const char* p) {
            int size = 0;
            // get len(s) and make sure len(s) >= len(p) - count(p, '*')
            for (auto q1 = s, q2 = p; *q1 != '\0' || *q2 != '\0'; q1++) {
                while (*q2 == '*') q2++;
                if (*q1 == '\0') {
                    if (*q2 != '\0') return false;
                    break;
                }
                if (*q2 != '\0') q2++;
                size++;
            }
            // vA[i] means whether p[0:j) matches s[0:i)
            vector<bool> vA(size + 1, false);
            vA[0] = true;  // "" matches ""
            vector<bool> vB;
            vB.reserve(vA.size());
            for (int j = 0; p[j] != '\0'; j++) {
                const char c = p[j];
                vB.push_back(vA[0] && c == '*');
                switch (c) {
                case '*':
                    // p[0:j] matches s[0:i) if p[0:j] matches s[0:i-1)
                    //                          or p[0:j) matches s[0:i)
                    for (int i = 1; i <= size; i++) {
                        vB.push_back(vB.back() || vA[i]);
                    }
                    break;
                case '?':
                    // p[0:j] matches s[0:i] if p[0:j) matches s[0:i)
                    for (int i = 0; i < size; i++) {
                        vB.push_back(vA[i]);
                    }
                    break;
                default:
                    // p[0:j] matches s[0:i] if p[0:j) matches s[0:i)
                    //                          and s[i] == p[j]
                    for (int i = 0; i < size; i++) {
                        vB.push_back(vA[i] && *(s+i) == c);
                    }
                }
                vB.swap(vA);
                vB.clear();
            }
            return vA.back();
        }
    };
    

  • 0
    J

    Much more readable than non-dp solution, and no need to consider any corner cases.


  • -3
    J

    Nice solution, but the indices in explanation is a little bit confusing. I believe it should be like this:

    For a 2d table, dp[i][j] would mean whether sub-pattern p[:i - 1] matches sub-string s[:j - 1]. Most tricky part is when the current pattern letter is *, suppose its index in p is i, p[:i ] will match sub-string s[:j ] if p[:i - 1] matches s[:j] or p[:i] matches s[:j - 1], namely current cell value is true if its top or its left is true. Since the current row only depends on the previous row, we can use two rolling lists to do the dp instead of a matrix.


  • 0
    C

    I think my indexes will work, because dp[i][j] means weather the substring of first icharacters of p match the substring of first j characters of s, inclusively.


  • 0
    J

    First i characters of p is p[:i-1], not p[:i+1] as your original post stated. Am I right?


  • 0
    G

    That's brilliant!


Log in to reply
 

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