题目描述(简单难度)

290、Word Pattern

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:

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

Example 2:

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

Example 3:

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

Example 4:

  1. Input: pattern = "abba", str = "dog dog dog dog"
  2. Output: false

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

判断字符串是否符合某个模式,类比于汉字,abb 型,就是喜洋洋,胖乎乎,每个汉字对应题目中的每个单词。

可以先做一下 205 题,基本上和这个题一模一样了,下边的思路也都是基于 205 题 去写了。

解法一

最简单的思路,利用 HashMappattern 的每个字母作为 keystr 的每个单词作为 value 。第一次遇到的 key 就加入到 HashMap 中,第二次遇到同一个 key,那就判断它的value 和当前单词是否一致。举个例子。

  1. pattern = "abba", str = "dog cat cat dog"
  2. a b b a
  3. dog cat cat dog
  4. ^
  5. i
  6. 第一次遇到 a, 加入到 HashMap
  7. HashMap = {a:dog}
  8. a b b a
  9. dog cat cat dog
  10. ^
  11. i
  12. 第一次遇到 b, 加入到 HashMap
  13. HashMap = {a: dog, b: cat}
  14. a b b a
  15. dog cat cat dog
  16. ^
  17. i
  18. HashMap = {a: dog, b: cat}
  19. 第二次遇到 b, 判断 HashMap b value 和当前的单词是否符合
  20. 符合的话继续判断, 不符合就返回 false
  21. a b b a
  22. dog cat cat dog
  23. ^
  24. i
  25. HashMap = {a: dog, b: cat}
  26. 第二次遇到 a, 判断 HashMap a value 和当前的单词是否符合
  27. 符合的话继续判断, 不符合就返回 false
  28. 遍历结束,返回 true

可以看一下相应的代码。

  1. public boolean wordPattern(String pattern, String str) {
  2. HashMap<Character, String> map = new HashMap<>();
  3. String[] array = str.split(" ");
  4. if (pattern.length() != array.length) {
  5. return false;
  6. }
  7. for (int i = 0; i < pattern.length(); i++) {
  8. char key = pattern.charAt(i);
  9. //当前 key 是否存在
  10. if (map.containsKey(key)) {
  11. if (!map.get(key).equals(array[i])) {
  12. return false;
  13. }
  14. } else {
  15. map.put(key, array[i]);
  16. }
  17. }
  18. return true;
  19. }

但上边的代码还是有问题的,我们只是完成了 patternstr 的映射,如果对于下边的例子是有问题的。

  1. pattern = "abba"
  2. str = "dog dog dog dog"

最直接的方法,在添加新的 key 的时候判断一下相应的 value 是否已经用过了。

  1. public boolean wordPattern(String pattern, String str) {
  2. HashMap<Character,String> map = new HashMap<>();
  3. String[] array = str.split(" ");
  4. if(pattern.length() != array.length){
  5. return false;
  6. }
  7. for(int i = 0; i < pattern.length();i++){
  8. char key = pattern.charAt(i);
  9. if(map.containsKey(key)){
  10. if(!map.get(key).equals(array[i])){
  11. return false;
  12. }
  13. }else{
  14. //判断 value 中是否存在
  15. if(map.containsValue(array[i])){
  16. return false;
  17. }
  18. map.put(key, array[i]);
  19. }
  20. }
  21. return true;
  22. }

虽然可以 AC 了,但还有一个问题,containsValue 的话,需要遍历一遍 value ,会导致时间复杂度增加。最直接的解决方法,我们可以把 HashMap 中的 value 存到 HashSet 中。

  1. public boolean wordPattern(String pattern, String str) {
  2. HashMap<Character, String> map = new HashMap<>();
  3. HashSet<String> set = new HashSet<>();
  4. String[] array = str.split(" ");
  5. if (pattern.length() != array.length) {
  6. return false;
  7. }
  8. for (int i = 0; i < pattern.length(); i++) {
  9. char key = pattern.charAt(i);
  10. if (map.containsKey(key)) {
  11. if (!map.get(key).equals(array[i])) {
  12. return false;
  13. }
  14. } else {
  15. // 判断 value 中是否存在
  16. if (set.contains(array[i])) {
  17. return false;
  18. }
  19. map.put(key, array[i]);
  20. set.add(array[i]);
  21. }
  22. }
  23. return true;
  24. }

当然还有另外一种思路,我们只判断了 patternstr 的映射,我们只需要再判断一次 strpattern 的映射就可以了,这样就保证了一一对应。

两次判断映射的逻辑是一样的,所以我们可以抽象出一个函数,但由于 pattern 只能看成 char 数组,这样的话会使得两次的 HashMap 不一样,一次是 HashMap<Character, String> ,一次是 HashMap<String, Character>。所以我们提前将 pattern 转成 String 数组。

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] array1 = str.split(" ");
  3. if (array1.length != pattern.length()) {
  4. return false;
  5. }
  6. String[] array2 = pattern.split("");
  7. //两个方向的映射
  8. return wordPatternHelper(array1, array2) && wordPatternHelper(array2, array1);
  9. }
  10. //array1 到 array2 的映射
  11. private boolean wordPatternHelper(String[] array1, String[] array2) {
  12. HashMap<String, String> map = new HashMap<>();
  13. for (int i = 0; i < array1.length; i++) {
  14. String key = array1[i];
  15. if (map.containsKey(key)) {
  16. if (!map.get(key).equals(array2[i])) {
  17. return false;
  18. }
  19. } else {
  20. map.put(key, array2[i]);
  21. }
  22. }
  23. return true;
  24. }

解法二

205 题 还介绍了另一种思路。

解法一中,我们通过对两个方向分别考虑来解决的。

这里的话,我们找一个第三方来解决。即,按照单词出现的顺序,把两个字符串都映射到另一个集合中。

第一次出现的单词(字母)映射到 1 ,第二次出现的单词(字母)映射到 2… 依次类推,这样就会得到一个新的字符串了。两个字符串都通过这样方法去映射,然后判断新得到的字符串是否相等 。

举个现实生活中的例子,一个人说中文,一个人说法语,怎么判断他们说的是一个意思呢?把中文翻译成英语,把法语也翻译成英语,然后看最后的英语是否相同即可。举个例子。

  1. pattern = "abba", str = "dog cat cat dog"
  2. 对于 abba
  3. a -> 1
  4. b -> 2
  5. 最终的得到的字符串就是 1221
  6. 对于 dog cat cat dog
  7. dog -> 1
  8. cat -> 2
  9. 最终的得到的字符串就是 1221
  10. 最终两个字符串都映射到了 1221, 所以 str 符合 pattern

代码的话,我们同样封装一个函数,返回映射后的结果。

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] array = str.split(" ");
  3. if(array.length!=pattern.length()){
  4. return false;
  5. }
  6. //判断映射后的结果是否相等
  7. return wordPatternHelper(pattern.split("")).equals(wordPatternHelper(array));
  8. }
  9. private String wordPatternHelper(String[] array) {
  10. HashMap<String, Integer> map = new HashMap<>();
  11. int count = 1;
  12. //保存映射后的结果
  13. StringBuilder sb = new StringBuilder();
  14. for (int i = 0; i < array.length; i++) {
  15. //是否已经映射过
  16. if (map.containsKey(array[i])) {
  17. sb.append(map.get(array[i]));
  18. } else {
  19. sb.append(count);
  20. map.put(array[i], count);
  21. count++;
  22. }
  23. }
  24. return sb.toString();
  25. }

为了方便,我们也可以将当前单词(字母)直接映射为当前单词(字母)的下标,省去 count 变量。

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] array = str.split(" ");
  3. if(array.length!=pattern.length()){
  4. return false;
  5. }
  6. //判断映射后的结果是否相等
  7. return wordPatternHelper(pattern.split("")).equals(wordPatternHelper(array));
  8. }
  9. private String wordPatternHelper(String[] array) {
  10. HashMap<String, Integer> map = new HashMap<>();
  11. //保存映射后的结果
  12. StringBuilder sb = new StringBuilder();
  13. for (int i = 0; i < array.length; i++) {
  14. //是否已经映射过
  15. if (map.containsKey(array[i])) {
  16. sb.append(map.get(array[i]));
  17. } else {
  18. sb.append(i);
  19. map.put(array[i], i);
  20. }
  21. }
  22. return sb.toString();
  23. }

上边我们是调用了两次函数,将字符串整体转换后来判断。我们其实可以一个单词(字母)一个单词(字母)的判断。第一次遇到的单词(字母)就给它一个 value ,也就是把下标给它。如果第二次遇到,就判断它们的 value 是否一致。

怎么判断是否是第一次遇到,我们可以通过判断 key 是否存在,但这样判断起来会比较麻烦。为了统一,我们可以给还不存在的 key 一个默认的 value,这样代码写起来比较统一。

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] array1 = str.split(" ");
  3. if (array1.length != pattern.length()) {
  4. return false;
  5. }
  6. char[] array2 = pattern.toCharArray();
  7. HashMap<String, Integer> map1 = new HashMap<>();
  8. HashMap<Character, Integer> map2 = new HashMap<>();
  9. for (int i = 0; i < array1.length; i++) {
  10. String c1 = array1[i];
  11. char c2 = array2[i];
  12. // 当前的映射值是否相同
  13. int a = map1.getOrDefault(c1, -1);
  14. int b = map2.getOrDefault(c2, -1);
  15. if (a != b) {
  16. return false;
  17. } else {
  18. map1.put(c1, i);
  19. map2.put(c2, i);
  20. }
  21. }
  22. return true;
  23. }

同样的思路,然后看一下 StefanPochmann 大神的 代码

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] words = str.split(" ");
  3. if (words.length != pattern.length())
  4. return false;
  5. Map index = new HashMap();
  6. for (Integer i = 0; i < words.length; ++i)
  7. if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
  8. return false;
  9. return true;
  10. }

他利用了 put 的返回值,如果 putkey 不存在,那么就插入成功,返回 null

如果 putkey 已经存在了,返回 key 是之前对应的 value

所以第一次遇到的单词(字母)两者都会返回 null,不会进入 return false

第二次遇到的单词(字母)就判断之前插入的 value 是否相等。也有可能其中一个之前还没插入值,那就是 null ,另一个之前已经插入了,会得到一个 value,两者一定不相等,就会返回 false

还有一点需要注意,for 循环中我们使用的是 Integer i,而不是 int i。是因为 map 中的 value 只能是 Integer

如果我们用 int i 的话,java 会自动装箱,转成 Integer。这样就会带来一个问题,put 返回的是一个 Integer ,判断对象相等的话,相当于判断的是引用的地址,那么即使 Integer 包含的值相等,那么它俩也不会相等。我们可以改成 int i 后试一试。

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] words = str.split(" ");
  3. if (words.length != pattern.length())
  4. return false;
  5. Map index = new HashMap();
  6. for (int i = 0; i < words.length; ++i)
  7. if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
  8. return false;
  9. return true;
  10. }

改成 int i 以后,就不能 AC 了。但你会发现当 pattern 的长度比较小时,代码是没有问题的,这又是为什么呢?

是因为当数字在 [-128,127] 的范围内时,对于同一个值,Integer 对象是共享的,举个例子。

  1. Integer a = 66;
  2. Integer b = 66;
  3. System.out.println(a == b); // ?
  4. Integer c = 166;
  5. Integer d = 166;
  6. System.out.println(c == d); // ?

大家觉得上边会返回什么?

是的,是 truefalse。当不在 [-128,127] 的范围内时,即使 Integer 包含的值相等,但由于是对象之间比较,依旧会返回 false

回到之前的问题,如果你非常想用 int ,比较两个值的时候,你可以拆箱去比较。但返回的有可能是 null,所以需要多加几个判断条件。

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] words = str.split(" ");
  3. if (words.length != pattern.length())
  4. return false;
  5. Map index = new HashMap();
  6. for (int i = 0; i < words.length; ++i) {
  7. Object a = index.put(pattern.charAt(i), i);
  8. Object b = index.put(words[i], i);
  9. if (a == null && b == null)
  10. continue;
  11. if (a == null || b == null)
  12. return false;
  13. if ((int) a != (int) b) {
  14. return false;
  15. }
  16. }
  17. return true;
  18. }

也可以通过 Object.equals 来判断两个 Integer 是否相等。

  1. public boolean wordPattern(String pattern, String str) {
  2. String[] words = str.split(" ");
  3. if (words.length != pattern.length())
  4. return false;
  5. Map index = new HashMap();
  6. for (int i=0; i<words.length; ++i)
  7. if (!Objects.equals(index.put(pattern.charAt(i), i),
  8. index.put(words[i], i)))
  9. return false;
  10. return true;
  11. }

其实和 205 题 用到的方法是一模一样的。此外,就是对 java 的装箱拆箱有了更多的了解。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情