290. 单词规律 与 205. 同构字符串
- 单词规律
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", str = "dog cat cat fish"
输出: false
示例 3:
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false
示例 4:
输入: pattern = "abba", str = "dog dog dog dog"
输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
参考：
https://leetcode.wang/leetcode-290-Word-Pattern.html
public boolean wordPattern(String pattern, String s) {
char[] charArr = pattern.toCharArray();
String[] splitArray = s.split(" ");
if (charArr.length != splitArray.length) {
return false;
}
Map<Character, String> characterStringMap = new HashMap<>();
Set<String> hashSet = new HashSet<>();
for (int i = 0; i < charArr.length; i++) {
char key = charArr[i];
//如果包含则 需要判断 值是不是与原来值相等
if (characterStringMap.containsKey(key)) {
String val = characterStringMap.get(key);
if (!val.equals(splitArray[i])) {
return false;
}
} else {
/**
* 解决如下bug 需要判断 value 是否已经存在
* String pattern = "abba";
* String str = "dog dog dog dog";
*/
if (hashSet.contains(splitArray[i])) {
return false;
}
characterStringMap.put(key, splitArray[i]);
hashSet.add(splitArray[i]);
}
}
return true;
}
看一下 StefanPochmann 大神的 代码。
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;
}
他利用了 put 的返回值，如果 put 的 key 不存在，那么就插入成功，返回 null。
如果 put 的 key 已经存在了，返回 key 是之前对应的 value。
所以第一次遇到的单词（字母）两者都会返回 null，不会进入 return false。
第二次遇到的单词（字母）就判断之前插入的 value 是否相等。也有可能其中一个之前还没插入值，那就是 null ，另一个之前已经插入了，会得到一个 value，两者一定不相等，就会返回 false。
还有一点需要注意，for 循环中我们使用的是 Integer i，而不是 int i。是因为 map 中的 value 只能是 Integer 。
当然也可以用 Objects.equals 来实现
public boolean wordPattern(String pattern, String str) {
String[] words = str.split(" ");
if (words.length != pattern.length())
return false;
Map<Object,Object> index = new HashMap();
for (int i=0; i<words.length; ++i)
if (!Objects.equals(index.put(pattern.charAt(i), i),
index.put(words[i], i)))
return false;
return true;
}
####### 205. 同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1:
输入: s = "egg", t = "add"
输出: true
示例 2:
输入: s = "foo", t = "bar"
输出: false
示例 3:
输入: s = "paper", t = "title"
输出: true
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/isomorphic-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路与 290 类似
public boolean isIsomorphic(String s, String t) {
if (s == null || t == null) {
return false;
}
if (s.length() != t.length()) {
return false;
}
Map<Object, Object> map = new HashMap<>();
Set<Object> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
if (!map.get(s.charAt(i)).equals(t.charAt(i))) {
return false;
}
} else {
if (set.contains(t.charAt(i))) {
return false;
}
map.put(s.charAt(i), t.charAt(i));
set.add(t.charAt(i));
}
}
return true;
}
用数组替换 map
public boolean isIsomorphic(String s, String t) {
if (s == null || t == null) {
return false;
}
if (s.length() != t.length()) {
return false;
}
int[] keyCountMap = new int[256];
int[] valCountMap = new int[256];
for (int i = 0; i < s.length(); i++) {
if (keyCountMap[s.charAt(i)] == 0) {
if (valCountMap[t.charAt(i)] > 0) {
return false;
}
keyCountMap[s.charAt(i)] = t.charAt(i);
valCountMap[t.charAt(i)]++;
} else {
if (keyCountMap[s.charAt(i)] != t.charAt(i)) {
return false;
}
}
}
return true;
}
