Java DP Accepted


  • 14
    D
    public class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length(), n = p.length();
            char[] ws = s.toCharArray();
            char[] wp = p.toCharArray();
            boolean[][] dp = new boolean[m+1][n+1];
            dp[0][0] = true;
            for (int j = 1; j <= n; j++)
                dp[0][j] = dp[0][j-1] && wp[j-1] == '*';
            for (int i = 1; i <= m; i++)
                dp[i][0] = false;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                	if (wp[j-1] == '?' || ws[i-1] == wp[j-1])
                		dp[i][j] = dp[i-1][j-1];
                	else if (wp[j-1] == '*')
                		dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
            return dp[m][n];
        }
    }

  • 1
    I

    My python DP solution is same idea as yours and it got TLE, I am not sure why...? Can you spot any difference?

    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            n, m = len(s), len(p)
            
            match = [[False for i in xrange(m + 1)] for j in xrange(n + 1)]
            match[0][0] = True
            
            for j in xrange(1, m + 1):
                if p[j - 1] == '*':
                    match[0][j] = match[0][j - 1]
                    
            for i in xrange(1, n + 1):
                for j in xrange(1, m + 1):
                    if p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                        match[i][j] = match[i - 1][j - 1]
                        
                    if p[j - 1] == '*':
                        match[i][j] = match[i][j - 1] or match[i - 1][j]
                        
            return match[-1][-1]

  • 0
    A

    @IWantToPass I tried the similar approach in Python just as you did and observed the Time Limit Exceeded problem. Don't know where the problem lies.

    Anyway the running time is O(mn) and space O(mn).


  • 1
    C

    @IWantToPass I got the same problem. TLE on Python DP


  • 0
    C

    What does DP stand for?


  • 0
    S

    @colas dynamic programming


  • 0
    S
    else if (wp[j-1] == '*')
                		dp[i][j] = dp[i-1][j] || dp[i][j-1];
    

    I have a question here. I think here we should add

    else if (wp[j-1] == '*')
                		dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i-1][j-1]; 
    

    because * can be ? in some cases.


  • 0
    F

    for (int i = 1; i <= m; i++)
    dp[i][0] = false;

    These code is no needed, because the default value of boolean array is false.


Log in to reply
 

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