[Wildcard match] TLE only happens on java


  • 1
    D

    I implemented almost the same logic segment in C and Java.But the Java code always be judged as TLE with this case.
    s="aaaaaaaaaaaaaaaaa..."
    p="aaaaaaaaaaaaaaaaa..."

    ...stands for 32317 repeated "a"

    Maybe my code is not the best one.But with this case, It only took less than 1 second to tell the correct answer.

    Does anyone can explain or give any suggestion?

    public class Solution {
    public boolean isMatch(String s, String p) {
    	
    	char[] sChar = s.toCharArray();
    	char[] pChar = p.toCharArray();
    	
    	int sind,pind;
    	int ss,ps;
    	
    	sind=pind=ss=ps=0;
    	
    	String tmp=p.replace("*", "");
    	if (!p.equals("")&&tmp.equals("")) {
    		return true;
    	}else if (s.equals("")) {
    		if (p.equals("")) {
    			return true;
    		}else {
    			return false;
    		}
    	}else if (p.equals("")) {
    		return false;
    	}
    	
    	while (true) {
    		
    		char schar = sChar[sind];
    		char pchar = pChar[pind];
    		
    		if (pchar==schar||pchar=='?') {
    			sind++;
    			pind++;
    		}else if (pchar=='*') {
    			pind++;
    			if (pind>=pChar.length) {
    				return true;
    			}
    			ps=pind;
    			ss=sind;
    		}else {
    			ss++;
    			sind=ss;
    			pind=ps;
    		}
    		
    		if (sind==sChar.length-1&&pind==pChar.length-1) {
    			return true;
    		}else if (sind>=sChar.length) {
    			while (pind<pChar.length&&pChar[pind]=='*') {
    				pind++;
    			}
    			
    			if (pind>=pChar.length){
    				return true;
    			}else {
    				ss++;
        			sind=ss;
        			pind=ps;
    			}
    		}else if (pind>=pChar.length) {
    			ss++;
    			sind=ss;
    			pind=ps;
    		}
    		
    		if (ss>=sChar.length) {
    			return false;
    		}
    	}
    	
    }
    

    }


  • 0
    S

    Could you please tell your algorithm explanation and add comments in your code? One more thing, correct your code format, your last } is out of code box.


  • 0
    H

    I have met the same problem, TLE for java.

    public class Solution {
        public boolean isMatch(String s, String p) {
        	String sBackup = null;
        	String pBackup = null;
        	int slen = s==null?0:s.length();
        	int plen = p==null?0:p.length();
        	while(slen > 0 ){
        		if(plen>0 && (p.charAt(0)=='?' || p.charAt(0) == s.charAt(0))) {
        			s = s.substring(1);
        			p = p.substring(1);
        			slen = s.length();
        			plen = p.length();
        		} else if(plen>0 && p.charAt(0) == '*') {
        			while(plen>0 &&p.charAt(0) == '*') {
        				p = p.substring(1);
        				plen = p.length();
        			}
        			if(plen == 0) {
        				return true;
        			}
        			sBackup = s;   //if p meet *, p and s can rollback anytime
        			pBackup = p;
        		} else {
        			if(sBackup == null) return false;
        			s = sBackup.substring(1);
        			sBackup = sBackup.substring(1);//important ("ab","*a")
        			p = pBackup;
        			slen = s.length();
        			plen = p.length();
        		}
        	}
        	while (plen>0 && p.charAt(0)=='*') {
        		p = p.substring(1);
    			plen = p.length();
        	}
        	return plen==0;
        }
    }

  • 1
    D

    The following is my solution in Java that passes the judge. I have some simple comments, but for a more detailed explanation and analysis on the complexity please see the slides on my blog http://decomplexify.blogspot.com/.

    public class Solution {
        public static boolean matchedWithQMark(String s, String t, int start) {
            if (start + t.length() > s.length()) { return false; }
            
            for (int j = 0; start+j < s.length() && j<t.length(); ++j) {
                if (s.charAt(start+j) != t.charAt(j) && t.charAt(j) != '?') {
                    return false;
                }
            }
            return true;
        }
               
        public boolean isMatch(String s, String t) {
            // remove stars from t, splitting t into pieces
            String[] tPieces = t.split("\\*+",-1);
            
            // special case: t has no star
            if (tPieces.length == 1) {
                return matchedWithQMark(s, t, 0) &&
                        s.length() == t.length();
            }
            
            String head = tPieces[0];
            String tail = tPieces[tPieces.length - 1];
            
            // special case: first piece does not fit,
            // or last piece does not fit, or they both
            // fit both overlap
            if (head.length() + tail.length() > s.length() ||
                    !matchedWithQMark(s, head, 0) ||
                    !matchedWithQMark(s, tail, s.length() - tail.length())) {
                return false;
            }
    
            int n = tPieces.length;
    
            // special case: no more pieces; it's a match
            if (n == 2) { return true; }
            
            // do not match the first piece
            int start = head.length();
            // do not match the last piece
            int sLen = s.length() - tail.length();
            
            // index for the next piece
            int i = 1;
            for (; i< tPieces.length - 1; ++i) {
                int tLen = tPieces[i].length();
                boolean found = false;
                while (start <= sLen - tLen) {
                    if (matchedWithQMark(s, tPieces[i], start)) {
                        found = true;
                        break;
                    }
                    start++;
                }
                if (!found) { return false; }
                start += tLen;
            }
            return i >= tPieces.length - 1;
        }
    }
    

  • 0
    A

    I read through your blog, it's great! Thanks for providing such excellent answer!


Log in to reply
 

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