Python DP solution


  • 28
    T
    class Solution:
    # @return a boolean
    def isMatch(self, s, p):
        length = len(s)
        if len(p) - p.count('*') > length:
            return False
        dp = [True] + [False]*length
        for i in p:
            if i != '*':
                for n in reversed(range(length)):
                    dp[n+1] = dp[n] and (i == s[n] or i == '?')
            else:
                for n in range(1, length+1):
                    dp[n] = dp[n-1] or dp[n]
            dp[0] = dp[0] and i == '*'
        return dp[-1]
    

    dp[n] means the substring s[:n] if match the pattern i

    dp[0] means the empty string '' or s[:0] which only match the pattern '*'

    use the reversed builtin because for every dp[n+1] we use the previous 'dp'

    add Java O(m*n) version code

    public boolean isMatch(String s, String p) {
        int count = 0;
        for (char c : p.toCharArray()) {
            if (c == '*')
                count++;
        }
        if (p.length() - count > s.length())
            return false;
        boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
        dp[0][0] = true;
        for (int j = 1; j <= p.length(); j++) {
            char pattern = p.charAt(j - 1);
            dp[j][0] = dp[j - 1][0] && pattern == '*';
            for (int i = 1; i <= s.length(); i++) {
                char letter = s.charAt(i - 1);
                if (pattern != '*') {
                    dp[j][i] = dp[j - 1][i - 1] && (pattern == '?' || pattern == letter);
                } else
                    dp[j][i] = dp[j][i - 1] || dp[j - 1][i];
            }
        }
        return dp[p.length()][s.length()];
    }

  • 0
    U
    This post is deleted!

  • 0
    W

    Awesome answer!


  • 0
    A

    This is very great! inspired by yours version.

    def isMatch(self, s, p):
        m = len(s)
        n = len(p)
    
        if n == 0 and m == 0:
            return True
        if n == 0 and m != 0:
            return False
        if p.count('*') == len(p):
            return True            
        if len(p) - p.count('*') > m:
            return False
    
        dp = [True] + [False]*m
        for cp in p:
            if cp != '*':
                for i in xrange(m, 0, -1): # m, m-1, .. 1
                    dp[i] = dp[i-1] and (cp=='?' or s[i-1] == cp)
            else:
                for i in xrange(1, m+1):
                    dp[i] = dp[i] or dp[i-1]
            dp[0] = dp[0] and cp=='*'
        
        return dp[m]

  • 0
    R

    Golang version:

    func isMatch(s string, p string) bool {
               
            dp := make([][]bool, len(p) + 1)
            for i,_:=range dp {
                dp[i] = make([]bool, len(s) + 1)
                for j, _:= range dp[i] {
                    dp[i][j] = false
                }
            }
            
            dp[0][0] = true
            
            for j:=1; j<=len(p); j++ {
                pattern := p[j-1]
                dp[j][0] = dp[j-1][0] && pattern == '*'
                for i:=1; i<=len(s); i++ {
                    letter := s[i-1]
                    if pattern != '*'{
                        dp[j][i] = dp[j-1][i-1] && (pattern == '?' || pattern == letter)
                    } else {
                        dp[j][i] = dp[j][i-1] || dp[j-1][i]
                    }
                }
            }
            return dp[len(p)][len(s)]
    }
    

Log in to reply
 

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