LeetCode 290. Word Pattern [Easy]

题目来源:https://leetcode.com/problems/word-pattern

题目难度:Easy

解答1[Java]:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
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;
}
}

思路

本解法是借助了 Java 的 HashMap 的特性。HashMap 的 put() 操作,如果 key 已经存在,那么就覆盖掉 key 原来的 value,并把原来的 value 当作返回值。

所以如果两个字符串模式相同,只要按顺序执行 put(),两个字符串执行中的返回值应该相同。

解答2[Java]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public boolean wordPattern(String pattern, String str) {
int n = pattern.length();
String[] strArr = str.split(" ");
if (strArr.length != n)
return false;
String[] dict = new String[26];
for (int i = 0; i < n; i++) {
char c = pattern.charAt(i);
if (dict[c - 'a'] == null)
dict[c - 'a'] = strArr[i];
else if (!dict[c - 'a'].equals(strArr[i]))
return false;
}

// if each character in pattern is different
// then each string in str should be different as well
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
if (i != j && dict[i] != null && dict[j] != null && dict[i].equals(dict[j]))
return false;
}
}
return true;
}

}

思路

使用字符串数组来进行判断。

第一遍是确定,如果 pattern 中有相同字母,那么 str 对应位置的字符串是否相同。

第二遍是确定,如果 pattern 中每个字母都不相同,那么 str 每个位置的字符也不能相同,如果相同,就不符合题意。