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. 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.

Using backtracking. If the mapping map contains the pattern char, check if str string starts with the mapping string, if not, return false, otherwise recursively check the next one. If the mapping map doesn't contain the pattern char, construct sub string from str and check if there is one mapping.

public boolean wordPatternMatch(String pattern, String str) {
        if (pattern.length() == 0 || str.length() == 0) {
            return false;
        }
        return checkMatch(pattern, str, new HashMap<>(), new HashSet<>());
    }

    private boolean checkMatch(String pattern, String str,
        Map<character, string> mapping, Set<string> words) {
        if (pattern.length() == 0 && str.length() == 0) {
            return true;
        } else if (pattern.length() == 0 || str.length() == 0) {
            return false;
        }
        char c = pattern.charAt(0);
        if (mapping.containsKey(c)) {
            String s = mapping.get(c);
            if (! str.startsWith(s)) {
                return false;
            }
            return checkMatch(pattern.substring(1), str.substring(s.length()),
                mapping, words);
        } else {
            int pos = 1;
            boolean isMatch = false;
            while (pos <= str.length()) {
                String sub = str.substring(0, pos);
                if (words.contains(sub)) {
                    continue;
                }
                mapping.put(c, sub);
                words.add(sub);
                isMatch |= checkMatch(pattern.substring(1), str.substring(pos),
                    mapping, words);
                if (isMatch) {
                    break;
                }
                mapping.remove(c);
                words.remove(sub);
                pos++;
            }
            return isMatch;
        }
    }