Time Limit Exceeded error for large test case. Space is O(length of P)


  • 0
    J

    I used DP to solve this problem. Table size is the length of p. Why I got Time Limit Exceeded for case "aaaaaaaaaaaaaaaa..."

    public class Solution {
    public boolean isMatch(String s, String p) {

        int m = s.length();
        int n = p.length();
        if(m ==0 && n == 0) return true;
        if(m!=0 && n==0) return false;
        if(m==0 && n!=0) return false;
        boolean[] table = new boolean[n+1];
        table[0] = true;
        
        if(p.charAt(0) == '*')
        {
            for(int i = 1; i <=n; i++) {
                table[i] = true;
            }
        }
        boolean current = false;
        boolean previous = false;
       
        for(int i = 1; i <=m; i++) {
            boolean temp = false;
            current = false;
            for(int j = 1; j <=n; j++) {
                    previous = current;
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?') {
                    current = table[j-1];
                    temp = temp || current;
                }
                else if(p.charAt(j-1) != '*' && s.charAt(i-1) != p.charAt(j-1)) {
                    current = false;
                    temp = temp || current;
                }
                else if (p.charAt(j-1) == '*')  {
                    current = temp;
                    }
                table[j-1] = previous; 
                }
            }
        
        return current;
    }
    

    }


Log in to reply
 

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