Question

Formatted question description: https://leetcode.ca/all/291.html

 291	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:

 pattern = "abab", str = "redblueredblue" should return true. (a->red, b->blue)
 pattern = "aaaa", str = "asdasdasdasd" should return true. (a->asd)
 pattern = "aabb", str = "xyzabcxzyabc" should return false.

 Notes:
 You may assume both pattern and str contains only lowercase letters.

Algorithm

To use HashMap to establish the mapping between pattern characters and words, you also need to use variables p and r to record the position of the pattern character and word string currently recursed to.

• In the recursive function, if p and r are equal to the length of the pattern string and the word string respectively, it means that the matching has ended successfully at this time, and ture is returned.
• On the contrary, if one is reached and the other is not, it means that the match has failed, and false is returned.
• If the above conditions are not met, take out the pattern character at the current position, and then traverse backward from position r of the word string, taking out one word each time,
  • If the pattern character already exists in the HashMap, and the corresponding word and the extracted word are also equal, then call the recursive function again in the next position,
    • If it returns true, then return true.
  • On the contrary, if the pattern character is not in the HashMap, it depends on whether other pattern characters have been mapped to the word currently taken out.
    • If not, create a new mapping and call the recursive function
    • Note that if the recursive function returns false, delete this mapping in the HashMap

Pitfall

Don’t forget below part during DFS.

map.remove(patternChar); // @note: need to remove, since this attempt is failed
inverseMap.remove(tentativeMatchString);

Code

Java

import java.util.HashMap;

public class Word_Pattern_II {

    public static void main(String[] args) {
        Word_Pattern_II out = new Word_Pattern_II();
        Solution s = out.new Solution();

        System.out.println(s.wordPattern("abab", "redblueredblue"));
        System.out.println(s.wordPattern("aaaa", "asdasdasdasd"));
        System.out.println(s.wordPattern("aabb", "xyzabcxzyabc"));
        System.out.println(s.wordPattern("aaaa", "asdyyyasdyyy")); // false
    }


    public class Solution {

        public boolean wordPattern(String pattern, String str) {

            HashMap<Character, String> map = new HashMap<>();
            HashMap<String, Character> inverseMap = new HashMap<>();

            return dfs(pattern, 0, str, 0, map, inverseMap);
        }

        // p: pattern length
        // r: word length
        boolean dfs(String pattern, int pattenIndex, String str, int strIndex, HashMap<Character, String> map, HashMap<String, Character> inverseMap) {

            if (pattenIndex == pattern.length() && strIndex == str.length()) {
                return true;
            }
            if (pattenIndex == pattern.length() || strIndex == str.length()) { // didn't hit above if but this one
                return false;
            }

            char patternChar = pattern.charAt(pattenIndex);

            for (int i = strIndex; i < str.length(); ++i) {
                String tentativeMatchString = str.substring(strIndex, i + 1);

                if (map.containsKey(patternChar) && map.get(patternChar).equals(tentativeMatchString)) {
                    if (dfs(pattern, pattenIndex + 1, str, i + 1, map, inverseMap)) {
                        return true;
                    }

                } else if (!map.containsKey(patternChar)) {

                    if (!inverseMap.containsKey(tentativeMatchString)) { // new pattern needed
                        map.put(patternChar, tentativeMatchString);
                        inverseMap.put(tentativeMatchString, patternChar);

                        if (dfs(pattern, pattenIndex + 1, str, i + 1, map, inverseMap)) {
                            return true;
                        }

                        map.remove(patternChar); // @note: need to remove, since this attempt is failed
                        inverseMap.remove(tentativeMatchString);
                    }
                }
            }
            return false;
        }
    }
}

All Problems

All Solutions