Leetcode: Word Pattern
LeetCode word pattern
2023-09-11 14:14:07 时间
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. Examples: pattern = "abba", str = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat cat dog" should return false. pattern = "abba", str = "dog dog dog dog" should return false. Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
注意这是一一映射,也就是说如果a->dog, b->dog,就应该return false,所以应该在HashMap基础上再加一层检查,即若不含该key,加入map之前应该检查map.values().contains(String)
第二遍:use HashMap和HashSet
1 public class Solution { 2 public boolean wordPattern(String pattern, String str) { 3 if (pattern==null || str==null) return false; 4 String[] all = str.split(" "); 5 6 if (pattern.length() != all.length) return false; 7 HashMap<Character, String> map = new HashMap<Character, String>(); 8 HashSet<String> set = new HashSet<String>(); 9 for (int i=0; i<pattern.length(); i++) { 10 char cur = pattern.charAt(i); 11 if (!map.containsKey(cur)) { 12 if (set.contains(all[i])) return false; 13 map.put(pattern.charAt(i), all[i]); 14 set.add(all[i]); 15 } 16 else { 17 if (!map.get(cur).equals(all[i])) 18 return false; 19 } 20 } 21 return true; 22 } 23 }
第一遍:
1 public class Solution { 2 public boolean wordPattern(String pattern, String str) { 3 if (pattern==null || str==null) return false; 4 String[] all = str.split(" "); 5 6 if (pattern.length() != all.length) return false; 7 HashMap<Character, String> map = new HashMap<Character, String>(); 8 for (int i=0; i<pattern.length(); i++) { 9 if (!map.containsKey(pattern.charAt(i))) { 10 if (map.values().contains(all[i])) return false; 11 map.put(pattern.charAt(i), all[i]); 12 } 13 else { 14 if (!map.get(pattern.charAt(i)).equals(all[i])) 15 return false; 16 } 17 } 18 return true; 19 } 20 }
相关文章
- Leetcode 之Largest Rectangle in Histogram(40)
- Leetcode 之Length of Last Word(38)
- Java实现 LeetCode 836 矩形重叠(暴力)
- Java实现 LeetCode 434 字符串中的单词数
- Java实现 LeetCode 289 生命游戏
- Java实现 LeetCode 31下一个排列
- 【LeetCode算法-58/66】Length of Last Word/Plus One
- [LeetCode] Majority Element II
- 〖Python自动化办公篇⑨〗- word文件自动化 - 设置Word全局样式和文本样式
- 【LeetCode-面试算法经典-Java实现】【144-Binary Tree Preorder Traversal(二叉树非递归前序遍历)】
- Leetcode 2235. 两整数相加
- Leetcode 1647. 字符频次唯一的最小删除次数(可以,终于解决)
- leetcode 19. 删除链表的倒数第 N 个结点 js实现
- LeetCode Length of Last Word
- LeetCode之Sort List
- 【LeetCode】剑指 Offer II 109. 开密码锁