导航
导航
文章目录
  1. 题目
  2. 翻译

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

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.

翻译

给出一个pattern和一个字符串str,判断str是否遵循一样的模式。
在这里遵循的意思是完全匹配,即pattern和str中的非空单词的双向对应。
例如:
pattern = “abba” , str = “dog cat cat dog” 应当返回true.
pattern = “abba” , str = “dog cat cat fish” 应当返回false.
pattern = “aaaa” , str = “dog cat cat dog” 应当返回false.
pattern = “abba” , str = “dog dog dog dog” 应当返回false.

与205. Isomorphic Strings类似。
设立一个hashmap,逐个遍历pattern和str中的单词,建立映射关系。因为要双向对应,所以非法的情况有以下:
1、pattern与str中的单词长度不一致;
2、对于同样的pattern字符,str中对应的单词不一致;
3、对于str中同样的单词,pattern的字符不一致:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public boolean wordPattern(String pattern, String str) {
String[] words = str.split(" ");
if (words.length != pattern.length()) return false;
Map<Character, String> patternWords = new HashMap<Character, String>();
for (int i = 0; i < words.length; i++) {
char c = pattern.charAt(i);
String word = words[i], mapWord = patternWords.get(c);
if (mapWord != null) {
if (!word.equals(mapWord)) return false;
} else if (patternWords.containsValue(word)) return false;
else patternWords.put(c, word);
}
return true;
}
}