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
- 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,
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) && 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 inverseMap.remove(tentativeMatchString); } } } return false; } } }
-
// OJ: https://leetcode.com/problems/word-pattern-ii/ // Time: O(PS) // Space: O(S) class Solution { public: 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; seen.insert(t); m[p[i]] = t; if (dfs(i + 1, k + 1)) return true; seen.erase(t); m.erase(p[i]); } } 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)): pathp.append(p[0]) 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 pathp.pop() paths.pop() return False return dfs(pattern, str, [], [], {})