Time Limit Exceeded with Java solution


  • 0
    S

    I think my solution is pretty straightforward - there are two base cases: the first character in the pattern is '' and the first character of the pattern is not ''. I have to be careful for some edge cases, but that is fine (like the length of the pattern is equal to 1, but the length of the string is less than 1). Here is my solution:

    public boolean isMatch(String s, String p) {
            //if the length of the pattern is 0 => check the length of the string for 0
            if(p.length()==0)
                return s.length()==0;
            //if the first character in the pattern is not '*' or if the pattern has lenght 1
            if(p.length()==1 || p.charAt(0) != '*'){
                if(s.length()<1 || (p.charAt(0) != '?' && p.charAt(0) != s.charAt(0)))
                    return false;
                return isMatch(s.substring(1), p.substring(1));
            }
            //if the first character of the pattern is '*' try to iterate over the shole string till mach is found
            else{
                int len = s.length();
                int i = -1;
                while(i < len){
                    if(isMatch(s.substring(i+1), p.substring(1)))
                        return true;
                    i++;
                }
                return false;
            }
        }
    

    Can someone explain me why I have time limit exceeded on the following test case:

    Last executed input:
    "abbabbbaabaaabbbbbabbabbabbbabbaaabbbababbabaaabbab",
    "aabbaaa*****aa"


  • 0
    Z

    the while cost much time
    I also got the same test case as you ,and I failed too,haha..


  • 0
    S

    How did you fixed it?


  • 0
    Z

    er,I haven't conqure this problem.
    maybe I should use dynamic programming,but I'm not good at this algorithm.


  • 0
    S

    I think your solution is a recursive version of DFS. The time complexity will be O(n!) And for this problem, once a '*' is matched correctly, you don't need to back trace any '*' that is before current'*'. By which I want to mean a DFS is not needed.


Log in to reply
 

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