【每日算法Day 21】字符串基础3
又是一天字符串中涉及统计与映射问题时哈希思想的应用。
# LeetCode 205. 同构字符串 (opens new window)
# 题目描述
给定两个字符串 s 和 t，判断它们是否是同构的。你可以假设 s 和 t 具有相同的长度。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
# 示例
示例 1:
输入: s = "foo", t = "bar"
输出: false
示例 2:
输入: s = "paper", t = "title"
输出: true
2
3
4
5
6
7
# 解题思路
既然时映射那很自然地就想到用HashMap来做（也可以自己用数组），扫描两个数组的对应位置，之前的key没有出现过就插入键值对，出现过则验证键值对是否匹配不匹配则返回false，直到最后都没有返回false则返回true。
public boolean isIsomorphic(String s, String t) {
return oneDirection(s, t) && oneDirection(t, s);
}
private boolean oneDirection(String s, String t) {
Map<Character,Character> map=new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char si=s.charAt(i),ti=t.charAt(i);
if (!map.containsKey(si)){
map.put(si, ti);
} else if (map.get(si)!=ti){
return false;
}
}
return true;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
值得一提的是不仅要对s->t做检查，也到对t->s做检查，以避免s=[a,b],t=[a,a]这样的两个值映射到同一个值的情况。
# LeetCode 290. 单词规律 (opens new window)
# 题目描述
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。
# 示例
示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
示例 2:
输入: pattern = "abba", str = "dog dog dog dog"
输出: false
2
3
4
5
6
7
# 解题思路
同上，只不过这次不是字符到字符的映射，而是字符串到字符串的映射，把pattern和str分别用""和" "分割即可。
public boolean wordPattern(String pattern, String str) {
if (pattern==null||str==null||pattern.length()==0||str.length()==0) return false;
String[] strs=str.split(" ");
String[] patterns=pattern.split("");
return match(strs,patterns)&&match(patterns,strs);
}
private boolean match(String[] a, String[] b) {
if (a.length!=b.length) return false;
Map<String,String> map = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (!map.containsKey(a[i])) {
map.put(a[i], b[i]);
} else if (!map.get(a[i]).equals(b[i])){
return false;
}
}
return true;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# LeetCode 242. 有效的字母异位词 (opens new window)
# 题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。说明: 你可以假设字符串只包含小写字母。
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
# 示例
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
2
3
4
5
6
7
# 解题思路
使用哈希数组来分别统计两个字符串中各字符的出现次数，如果两个哈希数组相等，则返回true，否则返回false。（如果输入字符串包含 unicode 字符则就要用到HashMap<Character,Integer>了）
public boolean isAnagram(String s, String t) {
return Arrays.equals(getHash(s),getHash(t));
}
private int[] getHash(String s) {
int[] hash=new int[128];
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i)]++;
}
return hash;
}
2
3
4
5
6
7
8
9
10
11