It seems that the test data for this problem is a litter bit weak.


  • 0
    Z

    An O(S.length()*P.length()) algorithm passed it with 985ms.
    But O(S.length() + P.length()) algorithm exists.
    I show the TLE data set in the main method.


    public class Solution {
    
    	boolean match(String s, String p) {
    		for (int i = 0; i < s.length(); ++i)
    			if (!(s.charAt(i) == p.charAt(i) || p.charAt(i) == '?'))
    				return false;
    		return true;
    	}
    
    	public boolean isMatch(String s, String p) {
    		if (s == null || p == null)
    			return false;
    		int front = p.indexOf('*'), back = p.length() - p.lastIndexOf('*') - 1;
    		if (front == -1)
    			return s.length() == p.length() && match(s, p);
    		if (!(front + back <= s.length()
    				&& match(s.substring(0, front), p.substring(0, front)) && match(
    					s.substring(s.length() - back), p.substring(p.length() - back))))
    			return false;
    		s = s.substring(front, s.length() - back);
    		p = p.substring(front, p.length() - back);
    		int i1 = 0, i2 = 0;
    		while (true) {
    			while (i2 < p.length() && p.charAt(i2) == '*')
    				++i2;
    			if (i2 == p.length())
    				break;
    			int st = i2;
    			while (p.charAt(i2) != '*')
    				++i2;
    			String piece = p.substring(st, i2);
    			while (i1 + piece.length() <= s.length()
    					&& !match(s.substring(i1, i1 + piece.length()), piece))
    				++i1;
    			if (i1 + piece.length() > s.length())
    				return false;
    			i1 += piece.length();
    		}
    		return true;
    	}
    
    	public static void main(String[] args) {
    		StringBuilder sb1 = new StringBuilder();
    		StringBuilder sb2 = new StringBuilder();
    
    		for (int i = 1; i <= 500000; i++)
    			sb1.append('a');
    		sb1.append('b');
    		for (int i = 1; i <= 500000; i++)
    			sb1.append('a');
    
    		sb2.append("***");
    		for (int i = 1; i <= 200000; i++)
    			sb2.append('a');
    		sb2.append('b');
    		for (int i = 1; i <= 200000; i++)
    			sb2.append('a');
    		sb2.append("***");
    
    		Solution solution = new Solution();
    		System.out.println(solution.isMatch(sb1.toString(), sb2.toString()));
    	}
    }

  • 0
    M
    This post is deleted!

  • 0
    M

    Does your linear time code work on s = "bbbbbbc" and p="*bbbc" ?


  • 0
    Z

    For my test case, my solution output 1.


  • 0
    H

    if s = aaaa..(100000 times), p = "?a?a?a?a?..."(100000 times), can the code work on linear time?


  • 0
    M

    Could you please explain your linear solution, I have been thinking for days but fail


  • 1
    S

    A seemingly viable linear solution by Yu:

    bool isMatch(const char *s, const char *p) {
            const char* star=NULL;
            const char* ss=s; 
            while (*s){
                if ((*p=='?')||(*p==*s)){s++;p++;continue;}
                if (*p=='*'){star=p++; ss=s;continue;}
                if (star){ p = star+1; s=++ss;continue;}
                return false;
            }
            while (*p=='*'){p++;}
            return !*p;
        }
    

    it simply record the last * position to regress when mismatch happens,and that works just fine

    different from Regex matching, stars here matches any characters instead of repeating the previous one,thus enabling the last recorded star mighty power :D

    consider this base case:

    Regex:". * b b * a" and "XXXXbbbXXXXa"

    Wildcard:" * b * a " and "XXXXbbbXXXXa"


  • 0
    Z

    I think your solution has a problem. Your code will get TLE in case below:
    ////////////////////////////////////////////////////////////
    int main() {
    string s1 = string(500000, 'a') + "b";
    string s2 = string("") + string(1000000, 'a') + "b";
    cout<<isMatch(s1.c_str(), s2.c_str())<<endl;
    }
    //////////////////////////////////////////////////////////
    My solution is trying to match the pattern string between 2 '
    ' use KMP algorithm.


  • 0
    M

    This solution is not linear. In fact it's O(|s|^2)


Log in to reply
 

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