Baozi Training Leetcode Solution 290: Word Pattern

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

Blogger:https://blog.baozitraining.org/2019/06/leetcode-solution-290-word-pattern.html

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 word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

Problem link

Video Tutorial

You can find the detailed video tutorial here

  • Youtube
  • B站

Thought Process

A very simple problem thus normally can solve it in multiple ways.

Encode string and patterns then compare

Since we are comparing "patterns" here, one straightforward way is encode the pattern into a string, then use the same encoding algorithm to encode the str array into a string, then compare the string. What encoding should we choose? Well it's not really an encoding per se. What I did is just convert any word or character to a character staring with ('a' + an index). If we see this character before, we just directly return from the hash map lookup. For example, "duck dog dog" would be encoded as "abb" while "bcc" would also be encoded as "abb".

Use bijection mapping

Note in the problem description it mentions it is a bijection mapping (i.e., a one to one mapping). As shown in the graph below, you see the differences between injection, surjection and bijection. That said, bijection does not allow duplicates. We can build a one to one mapping between the pattern and string, since it's bijection, if two characters in the pattern map to the same string, then it's not a valid bijection, therefore return false.

Solutions

Encode string and patterns then compare

 1  // This way will also work, just a little bit more work by encoding each string into the same one
 2     // Kinda similar to the isomorphic string
 3     public boolean wordPatternEncoding(String pattern, String str) {
 4         if (str == null || str.isEmpty() || pattern == null || pattern.isEmpty()) {
 5             return false;
 6         }
 7 
 8         String[] s = str.split(" ");
 9         if (pattern.length() != s.length) {
10             return false;
11         }
12 
13         // encode pattern
14         String patternEncoded = this.encodeString(pattern);
15         // encode the string array
16         String strEncoded = this.encodeArray(s);
17 
18         // compare
19         return patternEncoded.equals(strEncoded);
20     }
21 
22     private String encodeArray(String[] s) {
23         Map<String, Character> lookup = new HashMap<>();
24 
25         int index = 0; // starting from 'a'
26         StringBuilder sb = new StringBuilder();
27         for (String ss : s) {
28             if (lookup.containsKey(ss)) {
29                 sb.append(lookup.get(ss));
30             } else {
31                 char c = (char)('a' + index);
32                 sb.append(c);
33                 index++;
34                 lookup.put(ss, c);
35             }
36         }
37         return sb.toString();
38     }
39 
40     // encode it to base to a, this is not really encoding, but mapping a char to a completely different one using
41     // the same order as encodeArray
42     private String encodeString(String s) {
43         Map<Character, Character> lookup = new HashMap<>();
44         int index = 0; // starting from 'a'
45         StringBuilder sb = new StringBuilder();
46         
47         for (int i = 0; i < s.length(); i++) {
48             char c = s.charAt(i);
49             
50             if (lookup.containsKey(c)) {
51                 sb.append(lookup.get(c));
52             } else {
53                 char t = (char)('a' + index);
54                 sb.append(t);
55                 index++;
56                 lookup.put(c,  t);
57             }
58         }
59         
60         return sb.toString();
61     }

Time Complexity: O(N), N is the length of pattern or string array, we loop it 3 times, but still O(N) Space Complexity: O(N), N is the length of pattern or string array, we need the extra map and string to store the results

Use bijection mapping (Recommended)

 1 // I recommend this solution: just need map to keep the mapping relationship
 2     public boolean wordPattern(String pattern, String str) {
 3         if (pattern == null || pattern.length() == 0 || str == null || str.length() == 0) {
 4             return false;
 5         }
 6 
 7         String[] strs = str.trim().split(" ");
 8 
 9         if (pattern.length() != strs.length) {
10             return false;
11         }
12 
13         Map<Character, String> lookup = new HashMap<>();
14         // As it says, it is a bijection, so it needs to be 1 to 1 mapping, cannot exist a case one key maps to different value case
15         // E.g., need this set for abba, dog dog dog dog -> false case
16         Set<String> mapped = new HashSet<>();
17 
18         for (int i = 0; i < pattern.length(); i++) {
19             char c = pattern.charAt(i);
20 
21             if (lookup.containsKey(c)) {
22                 if (!lookup.get(c).equals(strs[i])) {
23                     return false;
24                 }
25             } else {
26                 // shit, just know put actually returns a V, which is the previous value, or null if not exist (or an associated null value)
27                 lookup.put(c, strs[i]);
28                 if (mapped.contains(strs[i])) {
29                     return false;
30                 }
31                 mapped.add(strs[i]);
32             }
33         }
34 
35         return true;
36     }

There is also a clever implementation like below. The key point is use the index to compare, if there is duplicate index, meaning there are two keys already mapped to the same value. Also, remember java put() returns a valid, not a void :)

 1 // Reference: https://leetcode.com/problems/word-pattern/discuss/73402/8-lines-simple-Java
 2 public boolean wordPattern(String pattern, String str) {
 3         String[] words = str.split(" ");
 4         if (words.length != pattern.length())
 5             return false;
 6         Map index = new HashMap();
 7         for (Integer i=0; i<words.length; ++i)
 8             if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
 9                 return false;
10         return true;
11     }

Time Complexity: N is the length of pattern or string array Space Complexity: O(N), N is the length of pattern or string array, we need a map regardless

References
  • Leetcode discussion with the clever implementation

原文发布于微信公众号 - 包子铺里聊IT(baozitraining)

原文发表时间:2019-06-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券