Python backtracking 48ms


  • 16
    Z

    Use dictionary to store patterns, and backtrack when mismatch happens.

    def wordPatternMatch(self, pattern, str):
        return self.dfs(pattern, str, {})
    
    def dfs(self, pattern, str, dict):
        if len(pattern) == 0 and len(str) > 0:
            return False
        if len(pattern) == len(str) == 0:
            return True
        for end in range(1, len(str)-len(pattern)+2): # +2 because it is the "end of an end"
            if pattern[0] not in dict and str[:end] not in dict.values():
                dict[pattern[0]] = str[:end]
                if self.dfs(pattern[1:], str[end:], dict):
                    return True
                del dict[pattern[0]]
            elif pattern[0] in dict and dict[pattern[0]] == str[:end]:
                if self.dfs(pattern[1:], str[end:], dict):
                    return True
        return False

  • 0
    S

    I was writing something very similar, but yours is 10 times faster. Then I realized it's all about the "end of end" trick. Thank you!


  • 1
    5
    str[:end] not in dict.values()
    

    I guess this line is O(n) time. if we keep track a reverse map, it could reduce.


  • 0
    A

    Same implementation in JAVA:

    public class Solution {
        public boolean wordPatternMatch(String pattern, String str) {
    		if (pattern == null || str == null) {
    			return false;
    		}
    		if (pattern.length() > str.length())
    			return false;
    		if (pattern.length() == 0) {
    			return str.length() == 0;
    		}
    
    		if (str.length() == 0)
    			return pattern.length() == 0;
    		Map<Character, String> map = new HashMap<Character, String>();
    		Map<String, Character> revMap = new HashMap<String, Character>();
    
    		return wordPatternMatch(pattern, str, map, revMap);
    	}
    
    	public boolean wordPatternMatch(String pattern, String str,
    			Map<Character, String> map, Map<String, Character> revMap) {
    		if(pattern.length() == 0)
    			return str.length() == 0;
    		for(int i = 1; i < str.length()-pattern.length()+2; i++){
    			if(!map.containsKey(pattern.charAt(0)) && !revMap.containsKey(str.substring(0, i))){
    				map.put(pattern.charAt(0), str.substring(0, i));
    				revMap.put(str.substring(0, i), pattern.charAt(0));
    				if(wordPatternMatch(pattern.substring(1), str.substring(i), map, revMap))
    					return true;
    				map.remove(pattern.charAt(0));
    				revMap.remove(str.substring(0,i));
    			}
    			else if(map.containsKey(pattern.charAt(0)) && map.get(pattern.charAt(0)).equals(str.substring(0,i))){
    				if(wordPatternMatch(pattern.substring(1), str.substring(i), map, revMap)){
    					return true;
    				}
    			}
    		}
    		return false;
    	}
    }

  • 0
    L

    what do you mean by "the end of the end", can you explain more detaily?


  • 1
    Z

    @leiyama001

    This is a general trick in backtracking, reduce the searching range.

    For example, if you have 5 patterns to match, but you have only 4 characters left, you know this is not going to yield a valid result, right? i.e. number of remaining patterns should always < number of characters.

    So the search range can be reduced by the number of remaining patterns.

    This idea is similar to #322 coil change problem,
    https://discuss.leetcode.com/topic/36306/python-11-line-280ms-dfs-with-early-termination-99-up


  • 2
    C

    @zhuyinghua1203 Thanks for sharing! I implemented your idea with two dicts to reduce the time of str[:end] not in dict.values()

    class Solution(object):
        def wordPatternMatch(self, pattern, str):
            def helper(pattern, string, forward={}, backward={}):
                if not pattern and string:
                    return False
    
                if not pattern and not string:
                    return True
    
                # abcde redblue
                # ^xxxx ^^^xxxx
                #   5       7
                # Try to match pattern `a` with at most 3 characters. 
                # That is 7 - 5 + 1, and the last + 1 is for Python range.
                for length in range(1, len(string) - len(pattern) + 1 + 1):
                    p, s = pattern[0], string[:length]
                    
                    if p not in forward and s not in backward:
                        forward[p] = s
                        backward[s] = p
    
                        if helper(pattern[1:], s, forward, backward):
                            return True
    
                        del forward[p]
                        del backward[s]
                    elif p in forward and forward[p] == s :
                        if helper(pattern[1:], s, forward, backward):
                            return True
                    else:
                        # Invalid, but we want to do another attempt so do not return yet.
                        pass
                return False
    
            return helper(pattern, str)
    

  • 0
    S

    @zhuyinghua1203 Thanks for your solution dude. To be honest, I find the "end of an end" pretty clever. I've +1'd your solution.

    Cheers :)


  • 0
    S

    Can you please explain the end of the end comment?


  • 0
    A

    @simply_khanh It is like at current iteration, we can map pattern[0] to str from 0 to len(str). However, as OP said there is no sense to match a 5-character pattern to a str with 4 characters. Thus the first letter can map first k letters of the str. Here len(str) - k <= len(pattern) -1, thus k max is len(str) - len(pattern) + 1. And we are slicing str using str[:end]. As it is exclusive for end with str slicing, so end should k + 1.


Log in to reply
 

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