Monday, October 26, 2015

Leetcode: Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Examples:
  1. pattern = "abab", str = "redblueredblue" should return true.
  2. pattern = "aaaa", str = "asdasdasdasd" should return true.
  3. pattern = "aabb", str = "xyzabcxzyabc" should return false.
Notes:
You may assume both pattern and str contains only lowercase letters.
Code (Java):
public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if ((pattern == null || pattern.length() == 0) && (str == null || str.length() == 0)) {
            return true;
        }
        
        if ((pattern == null || pattern.length() == 0) || (str == null || str.length() == 0)) {
            return false;
        }
        
        Map<Character, String> forwardMap = new HashMap<>();
        Map<String, Character> invertedMap = new HashMap<>();
        
        return wordPatternMatchHelper(0, pattern, 0, str, forwardMap, invertedMap);
    }
    
    private boolean wordPatternMatchHelper(int pStart, String pattern, 
                                      int sStart, String str, 
                                      Map<Character, String> forwardMap, 
                                      Map<String, Character> invertedMap) {
        if (pStart == pattern.length() && sStart == str.length()) {
            return true;
        }
        
        if (pStart >= pattern.length() || sStart >= str.length()) {
            return false;
        }
        
        char pChar = pattern.charAt(pStart);
        for (int i = sStart; i < str.length(); i++) {
            String curr = str.substring(sStart, i + 1);
            
            if ((!forwardMap.containsKey(pChar)) && (!invertedMap.containsKey(curr))) {
                forwardMap.put(pChar, curr);
                invertedMap.put(curr, pChar);
                
                if (wordPatternMatchHelper(pStart + 1, pattern, i + 1, 
                        str, forwardMap, invertedMap)) {
                    return true;
                }
                
                forwardMap.remove(pChar);
                invertedMap.remove(curr);
            } else if (forwardMap.containsKey(pChar) && invertedMap.containsKey(curr)) {
                String dict = forwardMap.get(pChar);
                char pCharDict = invertedMap.get(curr);
                
                // IMPORTANT !! If not equal, instead of returnning false immedidately,
                // We need to try other longer substrings. 
                if (!dict.equals(curr) || pCharDict != pChar) {
                    continue;
                }
                
                if (wordPatternMatchHelper(pStart + 1, pattern, i + 1, str, 
                        forwardMap, invertedMap)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Hi.. May I know the time complexity of this algorithm?

    ReplyDelete