Wildcard matching: Missing Test case?


  • 0
    M

    I was wondering if the following test case is missing:

    "abefcdgiescdfimde", "ab*cd?i*de"-> true
    

    OJ seems to pass all cases where you look for the first instance of the characters after the *, but does not seem to fail me if I do not add logic to check for a later instance of the characters.

    I.E. In my example the chars after the * are cd. If I only at the first cd after ab, I would say that the result is false, but in reality it is true.

    Below is the code I used. I used the following approach:

    1. Break pattern string into components that are *, ?, then any list of non-wild card chars
    2. Remove characters at the end of the input string that match non-* characters at the end
    3. Use the isMatch(ArrayList, ..) method to match the remaining pattern components

    The code as is will pass all of the tests by OJ.

    The commented out code in isMatch (to check against the * wildcard is what I needed to match my example above. However, this code never seems to complete when running the following test case:

    "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb", 
    "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb" 
    -> false
    

    I think my code runs in O(n^k) where k is the number of *'s in the pattern, so I guess it is not surprising it can't complete it.

    import java.util.ArrayList;
    
    
    public class Solution {
    
    public boolean isMatch(String s, String p) {
        
    	if (p == null || s == null || p.length() == 0 && s.length() != 0) 
    	{
    		return false;
    	}
    	
    	if (s.length() == 0 && (p.length() == 0 || "*".equals(p)))
    	{
    		return true;
    	}
    	
    	ArrayList<String> patterns = extractPatternComponents(p);
    	
    	// to improve performance, check any non * matches at end
    	while (patterns.size() > 0)
    	{
    		int lastIndex = patterns.size() - 1;
    		String lastPattern = patterns.get(lastIndex);
    		if ("*".equals(lastPattern))
    		{
    			break;
    		}
    		
    		patterns.remove(lastIndex);
    		if ("?".equals(lastPattern))
    		{
    			// make sure we have a char at the end
    			if (s.length() == 0)
    			{
    				return false;
    			}
    			
    			s = s.substring(0, s.length() - 1);
    		}
    		else
    		{
    			// make sure the end matches the last pattern
    			if (!s.endsWith(lastPattern))
    			{
    				return false;
    			}
    			
    			s = s.substring(0, s.length() - lastPattern.length());
    		}
    	}
    	
    	if (patterns.size() == 0)
    	{
    		return (s.length() == 0);
    	}
    	
    	return isMatch(patterns, 0, s);
    }
    
    /**
     * Check if the input string matches all of the remaining patterns
     * @param patterns List of patterns to match against
     * @param patternStart First index in pattern list to match
     * @param input Remaining input string to match against
     * @return True if we have a match
     */
    private boolean isMatch(ArrayList<String> patterns, int patternStart, String input)
    {
    	// if we hit the end of the patterns, make sure we have gone through the whole string
    	if (patternStart == patterns.size())
    	{
    		return input.length() == 0;
    	}
    	
    	int patternIndex = patternStart;
    	String nextPattern = patterns.get(patternIndex);
    	if ("*".equals(nextPattern))
    	{
    		
    		// if the last pattern is a * then we are done
    		if (patternIndex == patterns.size() - 1)
    		{
    			return true;
    		}
    		
    		patternIndex = patternStart + 1;
    		while (patternIndex < patterns.size())
    		{
    			nextPattern = patterns.get(patternIndex);
    			
    			if ("*".equals(nextPattern))
    			{
    				// do a recursive call if we have another * now
    				return isMatch(patterns, patternIndex, input);
    			}
    			if ("?".equals(nextPattern))
    			{
    				// if next pattern is a ? just match one character and look for next pattern
    				if (input.length() == 0)
    				{
    					return false;
    				}
    				input = input.substring(1);
    			}
    			else
    			{
    				// in this case we check all possible matches
    	//					int checkIndex = -1;
    	//					String subInput = input;
    	//					while ((checkIndex = subInput.indexOf(nextPattern)) > -1)
    	//					{
    	//						if (isMatch(patterns, patternIndex, subInput.substring(checkIndex)))
    	//						{
    	//							return true;
    	//						}
    	//						//return false;
    	//						
    	//						checkIndex++;
    	//						subInput = subInput.substring(checkIndex);
    	//					}
    	//					
    	//					return false;
    				
    				// in this case we just check for the first match of the pattern
    				int firstMatchIndex = input.indexOf(nextPattern);
    				return (firstMatchIndex >= 0 && isMatch(patterns, patternIndex, input.substring(firstMatchIndex)));
    				
    			}
    			
    			patternIndex++;
    		}
    		
    		// we shouldn't get here, but if we do then we have a failure
    		return false;
    	}
    	else if ("?".equals(nextPattern))
    	{
    		if (input.length() == 0)
    		{
    			return false;
    		}
    		
    		return isMatch(patterns, patternIndex + 1, input.substring(1));
    	}
    	else
    	{
    		// match the chars in the pattern
    		if (input.indexOf(nextPattern) != 0)
    		{
    			return false;
    		}
    		
    		return isMatch(patterns, patternIndex + 1, input.substring(nextPattern.length()));
    	}
    }
    
    
    /**
     * Extract a list of patterns components that are in the pattern string
     * @param pattern Pattern to match
     * @return List of pattern components
     */
    private ArrayList<String> extractPatternComponents(String pattern)
    {
    	ArrayList<String> components = new ArrayList<String>();
    	if (pattern == null || pattern.length() == 0)
    	{
    		return null;
    	}
    	
    	int startIndex = 0;
    	for (int i = 0; i < pattern.length(); i++)
    	{
    		char current = pattern.charAt(i);
    		if (current == '*' || current == '?')
    		{
    			// new wildcard
    			if (startIndex != i)
    			{
    				// we need to add everything before the wildcard first
    				components.add(pattern.substring(startIndex, i));
    			}
    			// if we have ** just consolidate it to a single *
    			if (!(current == '*' && components.size() > 0 && 
    									"*".equals(components.get(components.size() - 1))))
    			{
    				components.add(pattern.substring(i, i + 1));
    			}
    			
    			startIndex = i + 1;
    		}
    	}
    	
    	// handle pattern at end
    	if (startIndex < pattern.length())
    	{
    		String remaining = pattern.substring(startIndex);
    		if (!(remaining == "*" && components.size() > 0 && 
    				components.get(components.size() - 1) == "*"))
    		{
    			components.add(remaining);
    		}
    	}
    	
    	return components;
    }
    }

  • 0
    S

    Thanks @msabin. Can you share your AC solution which should fail on this test case?


  • 0
    M

    I updated my post with my code.


Log in to reply
 

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