LeetCode - Word Pattern II

WordPatternII.java

// 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:
// pattern = "abab", str = "redblueredblue" should return true.
// pattern = "aaaa", str = "asdasdasdasd" should return true.
// pattern = "aabb", str = "xyzabcxzyabc" should return false.
// Notes:
// You may assume both pattern and str contains only lowercase letters.

public boolean wordPatternMatch(String pattern, String str) {
    if(pattern == null || str == null) return false;
    Map<Character, String> map = new HashMap<Character, String>();
    return helper(pattern, str, 0, 0, map);
}

private boolean helper(String pattern, String str, 
                       int p_pos, int s_pos, Map<Character, String> map){
    if(p_pos >= pattern.length() || s_pos >= str.length()){
        if(p_pos == pattern.length() && s_pos == str.length()) return true;
        else return false;
    }
    char c = pattern.charAt(p_pos);
    for(int i = s_pos; i < str.length(); i++){
        String value = str.substring(s_pos, i + 1);
        int size = map.size();
        if(isValid(c, value, map)){
            boolean flag = map.size() > size ? true : false;
            if(helper(pattern, str, p_pos + 1, i + 1, map)) return true;
            if(flag) map.remove(c);
        }
    }
    return false;
}

private boolean isValid(char c, String value, Map<Character, String> map){
    if(map.containsKey(c)){
        if(!map.get(c).equals(value)) return false;
    } else{
        if(map.containsValue(value)) return false;
        map.put(c, value);
    }
    return true;
}


// better solution?