Baozi Leetcode Solution 290: Word Pattern
Problem Statement
pattern and a string str, find if str follows the same pattern.pattern and a non-empty word in str.Input: pattern ="abba", str ="dog cat cat dog"
Output: true
Input:pattern ="abba", str ="dog cat cat fish"
Output: false
Input: pattern ="aaaa", str ="dog cat cat dog"
Output: false
Input: pattern ="abba", str ="dog dog dog dog"
Output: false
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
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.
 |
| Ref: https://en.wikipedia.org/wiki/Injective_function |
Solutions
Encode string and patterns then compare
// This way will also work, just a little bit more work by encoding each string into the same one
// Kinda similar to the isomorphic string
public boolean wordPatternEncoding(String pattern, String str) {
if (str == null || str.isEmpty() || pattern == null || pattern.isEmpty()) {
return false;
} String[] s = str.split(" ");
if (pattern.length() != s.length) {
return false;
} // encode pattern
String patternEncoded = this.encodeString(pattern);
// encode the string array
String strEncoded = this.encodeArray(s); // compare
return patternEncoded.equals(strEncoded);
} private String encodeArray(String[] s) {
Map<String, Character> lookup = new HashMap<>(); int index = 0; // starting from 'a'
StringBuilder sb = new StringBuilder();
for (String ss : s) {
if (lookup.containsKey(ss)) {
sb.append(lookup.get(ss));
} else {
char c = (char)('a' + index);
sb.append(c);
index++;
lookup.put(ss, c);
}
}
return sb.toString();
} // encode it to base to a, this is not really encoding, but mapping a char to a completely different one using
// the same order as encodeArray
private String encodeString(String s) {
Map<Character, Character> lookup = new HashMap<>();
int index = 0; // starting from 'a'
StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i); if (lookup.containsKey(c)) {
sb.append(lookup.get(c));
} else {
char t = (char)('a' + index);
sb.append(t);
index++;
lookup.put(c, t);
}
} return sb.toString();
}
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)
// I recommend this solution: just need map to keep the mapping relationship
public boolean wordPattern(String pattern, String str) {
if (pattern == null || pattern.length() == 0 || str == null || str.length() == 0) {
return false;
} String[] strs = str.trim().split(" "); if (pattern.length() != strs.length) {
return false;
} Map<Character, String> lookup = new HashMap<>();
// 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
// E.g., need this set for abba, dog dog dog dog -> false case
Set<String> mapped = new HashSet<>(); for (int i = 0; i < pattern.length(); i++) {
char c = pattern.charAt(i); if (lookup.containsKey(c)) {
if (!lookup.get(c).equals(strs[i])) {
return false;
}
} else {
// shit, just know put actually returns a V, which is the previous value, or null if not exist (or an associated null value)
lookup.put(c, strs[i]);
if (mapped.contains(strs[i])) {
return false;
}
mapped.add(strs[i]);
}
} return true;
}
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 :)
// Reference: https://leetcode.com/problems/word-pattern/discuss/73402/8-lines-simple-Java
public boolean wordPattern(String pattern, String str) {
String[] words = str.split(" ");
if (words.length != pattern.length())
return false;
Map index = new HashMap();
for (Integer i=0; i<words.length; ++i)
if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
return false;
return true;
}
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
最新文章
- 解析sql语句中left_join、inner_join中的on与where的区别
- 动态平衡二叉搜索树的简易实现，Treap 树
- codeforces 711B B. Chris and Magic Square(水题)
- 对原型prototype的详解
- Socket 两平台互相 通信 .NET
- 结构体定义 typedef struct 用法详解和用法小结
- jquery选择器之层级过滤选择器
- web前端 ajax请求上传图片数据类型处理
- 深蓝词库转换2.4版发布，支持最新的搜狗用户词库备份bin格式
- MySQL导入数据报 Got a packet bigger than‘max_allowed_packet’bytes 错误的解决方法
- Vue Resource root options not used?
- CIFAR-10数据集读取
- Kettle从excel导入数据到sql server
- 利用sed把一行的文本文件改成每句一行
- 20145313张雪纯exp7
- 第九章 对称加密算法--IDEA
- MongoDB Python官方驱动 PyMongo 的简单封装
- BZOJ 4726 POI 2017 Sabota? 树形DP
- 利用层的table-row、table-cell属性进行页面布局
- 简单的Slony-I设置实例 II