Word Pattern II(Hard)

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.

给一个pattern和一个string, 问string是否满足pattern. 这次string里面的word没有空格.

Java代码：

public boolean wordPatternMatch(String pattern, String str) {
    return helper(pattern, str, 0, new HashMap<Character, String>(),
        new HashMap<String, Character>());
}


private boolean helper(String pattern, String str, int patternPos,
                           Map<Character, String> char2string,
                           Map<String, Character> string2char) {
    if (patternPos == pattern.length()) {
        if (str.length() == 0) {
            return true;
        }
        return false;
    }

    // there are only two cases of valid mapping
    // case 1. char and substring exist as key in two maps, and map to each
    // other
    // case 2. char and substring do not exist in the two maps, then we
    // insert the mapping
    char currPat = pattern.charAt(patternPos);
    if (!char2string.containsKey(currPat)) {
        for (int l = 1; l <= str.length() - (pattern.length() - patternPos)
                    + 1; l++) {
            String substr = str.substring(0, l);
            // check if case 2 is satisfied
            if (!string2char.containsKey(substr)) {
                char2string.put(currPat, substr);
                string2char.put(substr, currPat);

                if (helper(pattern, str.substring(l), patternPos + 1,
                            char2string, string2char)) {
                    return true;
                }

                char2string.remove(currPat, substr);
                string2char.remove(substr, currPat);
            }
        }
    } else {
        // check if case 1 is satisfied
        String value = char2string.get(currPat);
        if (str.startsWith(value) &&
            string2char.containsKey(value) &&
            string2char.get(value) == currPat &&
            helper(pattern, str.substring(value.length()),
                    patternPos + 1, char2string, string2char)) {

                return true;
        }
    }
    return false;
}

References

1 Share my Java backtracking solution

2 Word Pattern II

3 Solution from LeetCode Discussion

4 Word Pattern