Why my code is corrent in Eclipse,but TLE in LeetCode?


  • 1
    F
    public class Solution {
        public boolean isMatch(String s, String p) {
    	    if (s.length()==0 && p.length()==0) return true;
    	    else if (p.length()==0) return false;
    	    else if (p.length()==1) 
    	    {
    	   	     if (p.charAt(0)=='.' && s.length()==1) return true;
    	 	     else return false;
    	    }
     	    else if (p.charAt(1)=='*')
    	    {
    		     if (p.charAt(0)=='.')
    		     {
    		   	     if (s.length()==0) return true;
    			     for (int i=0;i<s.length();i++)
    			     {
    			 	     if (isMatch(s.substring(i),p.substring(2))) return true;
    			     }
    			     return false;
    	    	 }
      		     else
    		     {
    			     if (s.length()==0) return true;
    			     for (int i=0;i<s.length();i++)
    			     {
    				     if (isMatch(s.substring(i),p.substring(2))) return true;
    				     if (s.charAt(i)!=p.charAt(0)) break;
    			     }
    			     return false;
    		     }
    	    }
    	    else if (s.length()==0) return false;
    	    else if (p.charAt(0)=='.') return isMatch(s.substring(1),p.substring(1));
    	    else if (s.charAt(0)==p.charAt(0)) return isMatch(s.substring(1),p.substring(1));
    	    else return false;
        }
    }

  • 0
    M

    TLE doesn't actually mean that the algorithm is stuck, just that it's not as efficient as it could be, and so takes a longer time than necessary. It does occur when there's an infinite loop inside your solution, but in that case, trying it in your IDE would fail as well.

    Since Eclipse ran it and returned an answer, the "took too long" version of TLE is the one occurring here.
    I'm not certain, but from your code, I believe what is happening is that you are doing some of the evaluations multiple times.

    For example, in "a*.*b", "aaaaaaccccccba", the algorithm will evaluate a* as increasing numbers of the a's, but then check the remainder of the string against ".*b". This works well, except ".*b" will evaluate the string with 4 a's as part of the string with 5 a's, then evaluate it again when a* advances another step. If you store the result in some manner, you won't need to redo the work, and will likely avoid TLE.


  • 0
    C

    String.substring() is time consuming, which will return a new String object. And creating an object in Java is expensive, you should try to avoid it.


Log in to reply
 

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