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

• 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;
}
``````

}

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