Formatted question description:

 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.


 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.

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


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


Don’t forget below part during DFS.

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



  • 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 = 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) && inverseMap.containsKey(tentativeMatchString) && inverseMap.get(tentativeMatchString).equals(patternChar)) {
                        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
                return false;
  • // OJ:
    // Time: O(PS)
    // Space: O(S)
    class Solution {
        bool wordPatternMatch(string p, string s) {
            unordered_map<char, string> m;
            unordered_set<string> seen;
            function<bool(int,int)> dfs = [&](int i, int j) {
                if (i == p.size()) return j == s.size();
                if (m.count(p[i])) {
                    auto t = m[p[i]];
                    return s.substr(j, t.size()) == t && dfs(i + 1, j + t.size());
                } else {
                    string t;
                    for (int k = j; k < s.size(); ++k) {
                        t += s[k];
                        if (seen.count(t)) continue;
                        m[p[i]] = t;
                        if (dfs(i + 1, k + 1)) return true;
                return false;
            return dfs(0, 0);
  • class Solution(object):
      def wordPatternMatch(self, pattern, str):
        :type pattern: str
        :type str: str
        :rtype: bool
        def dfs(p, s, pathp, paths, visited):
          if len(p) == len(s) == 0:
            return True
          if len(p) == 0 or len(p) > len(s):
            return False
          for i in range(0, len(s)):
            paths.append(s[:i + 1])
            if len(pathp) == len(paths) and len(set(paths)) == len(set(pathp)) == len(set(zip(paths, pathp))):
              if dfs(p[1:], s[i + 1:], pathp, paths, visited):
                return True
          return False
        return dfs(pattern, str, [], [], {})

All Problems

All Solutions