# Baozi Training Leetcode Solution 291: Word Pattern II

Blogger: https://blog.baozitraining.org/2019/07/leetcode-solution-291-word-pattern-ii.html

B站: https://www.bilibili.com/video/av59261770/

### Problem Statement

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

Example 1:

```Input: pattern = "abab", str = "redblueredblue"
Output: true```

Example 2:

```Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true```

Example 3:

```Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false```

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

### Video Tutorial

You can find the detailed video tutorial here

• B站

### Thought Process

It is quite similar to Word Pattern and Isomorphic String problem, where we would keep a mapping from char to a string while also ensure there would be a one to one mapping, i.e., bijection mapping. The tricky part is it seems there are way many combinations of the mapping, how can we efficiently solve them? Maybe we could list all the combinations? Maybe we could use DP since it is string related and only ask for true/false result? How to list all combinations? Think about this way, let's say you have pattern = "aba" and str = "redbluered", since one char in pattern can map to any string length >= 1 in str, it is equivalent to divide up str into 3 parts (length of pattern) and check all cases. For instance, the cut of the words is like below:

1. r | e | d b l u e r e d
2. r | e d | b l u e r e d
3. r | e d b | l u e r e d
4. r | e d b l | u e r e d
5. r | e d b l u | e r e d
6. r | e d b l u e | r e d
7. r | e d b l u e r | e d
8. r | e d b l u e r e | d
9. r e | d | b l u e r e d
10. r e | d b | l u e r e d
11. r e | d b l | u e r e d
12. r e | d b l u | e r e d
13. r e | d b l u e | r e d
14. r e | d b l u e r | e d
15. r e | d b l u e r e | d
16. r e d | b | l u e r e d
17. .....

In general, if the length of pattern is M, the str length is N, the time complexity of this brute force method is O(N^M), more accurately, it should be

DP solution does not work since we cannot easily get a deduction formula :(

### Solutions

#### Brute force list all the combos

For each character in pattern, try to map any possible remaining strings in str from length 1 to the end. During this process, need to make sure the string mapping is bijection (no two chars in pattern map to the same string in str) and if a mapping has been seen before, continue use that mapping

A DFS recursion would be the implementation. A few caveats in implementation

• Remember to reset the map and set after recursion returned false
• When there is a bijection mapping, should continue instead of directly break
``` 1  public boolean wordPatternMatch(String pattern, String str) {
2         if (pattern == null || str == null) {
3             return false;
4         }
5
6         Map<Character, String> lookup = new HashMap<>();
7         Set<String> dup = new HashSet<>();
8
9         return this.isMatch(pattern, str, lookup, dup);
10     }
11
12     // DFS recursion to list out all the possibilities
13     public boolean isMatch(String pattern, String str, Map<Character, String> lookup, Set<String> dup) {
14         if (pattern.length() == 0) {
15             return str.length() == 0;
16         }
17
18         char c = pattern.charAt(0);
19
20         if (lookup.containsKey(c)) {
21             String mappedString = lookup.get(c);
22             if (mappedString.length() > str.length()) {
23                 return false;
24             }
25
26             // could use str.startsWith(mappedString)
27             if (!mappedString.equals(str.substring(0, mappedString.length()))) {
28                 return false;
29             }
30
31             return this.isMatch(pattern.substring(1), str.substring(mappedString.length()), lookup, dup);
32
33         } else {
34             for (int i = 1; i <= str.length(); i++) {
35                 String mappingString = str.substring(0, i);
36                 if (dup.contains(mappingString)) {
37                     // not a bijection mapping, not not return false, but continue
38                     continue;
39                 }
40
41                 lookup.put(c, mappingString);
43                 if (this.isMatch(pattern.substring(1), str.substring(i), lookup, dup)) {
44                     return true;
45                 }
46                 // reset value for next recursion iteration for backtracking
47                 lookup.remove(c);
48                 dup.remove(mappingString);
49             }
50         }
51
52         return false;
53     }```

Time Complexity: O(N^M), or C(N^M) to be exact. Pattern length is M, str length is N Space Complexity: O(M), Pattern length is M, str length is N. We use a map and a set to store the lookup, but at one time, the map should not exceed the pattern size, so is the set

0 条评论

• ### Baozi Training Leetcode Solution 290: Word Pattern

博客园：https://www.cnblogs.com/baozitraining/p/11087658.html

• ### Baozi Training Leetcode solution 124:BinaryTree Maximum Path Sum

Leetcode solution 124: Binary Tree Maximum Path Sum

• ### "Turning Video" 招人 & Data Engineer Roadmap

图灵视频成立于2017年3月，由硅谷基金Village Global(比尔盖茨, 杰夫·贝佐斯等的早期基金), 硅谷基金Basis Set , AI List，...

• ### 深度残差收缩网络详解

深度残差网络ResNet获得了2016年IEEE Conference on Computer Vision and Pattern Recognition的最...

• ### 2-3 链表拼接 (20 分)

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### 一文探讨堆外内存的监控与回收

记得那是一个风和日丽的周末，太阳红彤彤，花儿五颜六色，96 年的普哥微信找到我，描述了一个诡异的线上问题：线上程序使用了 NIO FileChannel 的 堆...

• ### 一文探讨堆外内存的监控与回收

记得那是一个风和日丽的周末，太阳红彤彤，花儿五颜六色，96 年的普哥微信找到我，描述了一个诡异的线上问题：线上程序使用了 NIO FileChannel 的 堆...

• ### PAT 1008

The highest building in our city has only one elevator. A request list is made u...

• ### NASA借助机器人制造复合材料

本月26日，弗吉尼亚州汉普顿NASA兰利研究中心将迎来高级集成装配机器人ISAAC助力研究人员在复合材料方面的制造工作。 ISAAC机器人的目的在于消除兰利...

• ### 腾讯云在这家酒店，开了一个通往未来的入口……

酒店采用腾讯云人脸识别及物联网技术，与酒店系统、公安系统数据打通，入住时“刷个脸”即可完成身份核验，简化入住流程，提高酒店服务效率。