1.有效的字母异位词（242-易）
题目描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词（字母相同位置不同）。进阶问题的核心点在于「字符是离散未知的」
示例：
输入: s = "anagram", t = "nagaram"
输出: true
输入: s = "rat", t = "car"
输出: false
思路：本题核心是记录出现字母的次数（数组或者hashmap），当两个字符串出现字母类别相同且数量相等，则为异位词。有两种思路：
- hashmap键值对进行记录是比较经典的方法。
- 也可以直接用数组记录字符出现的次数。
代码实现：
class Solution {
// hashmap
public boolean isAnagram1(String s, String t) {
if (s.length() != t.length()) {
return false;
}
HashMap<Character, Integer> map = new HashMap<>();
for (char cs : s.toCharArray()) {
map.put(cs, map.getOrDefault(cs, 0) + 1);
}
for (char ct : t.toCharArray()) {
map.put(ct, map.getOrDefault(ct, 0) - 1);
if (map.get(ct) == -1) {
return false;
}
}
return true;
}
// 数组计数(推荐)
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
// 记录字母出现的次数
int[] counts = new int[26];
for (char cs : s.toCharArray()) {
counts[cs - 'a']++;
}
for (char ct : t.toCharArray()) {
counts[ct - 'a']--;
}
for (int num : counts) {
if (num != 0) {
return false;
}
}
return true;
}
}
ps：这个比较耗时，hashmap初始容量16，感觉扩容耗时！！
拓展：字母的异位词分组（T49）
思路：如何知道两个单词是异位词？排序或者计数！
- 排序：将排序后的字符串作为键（先转成字符数组，根据ascii码进行排序）
- 计数：自定义编码作为键
注意：map的key必须是String类型！不能是字符数组，原因是String重写了HashCode()和equalls()map.values()获取map的所有值。
代码实现：
class Solution {
// 排序法(对每个字母进行重排序)
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, ArrayList<String>> map = new HashMap<>();
for (String str : strs) {
char[] chs = str.toCharArray();
Arrays.sort(chs);
// 特别注意：要将字符数组转化为字符串，因为String实现了equals和hashCode方法
String key = String.valueOf(chs);
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(str);
}
return new ArrayList(map.values());
}
// 计数法（两个数互为异位词：字母出现的次数相同）
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, ArrayList<String>> map = new HashMap<>();
for (String str : strs) {
char[] chs = str.toCharArray();
int[] counts = new int[26];
for (char c : chs) {
counts[c - 'a']++;
}
// 将字符数组编码为字符串，比如将 [b,a,a,a,b,c] 编码成 a3b2c1
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char)('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(str);
}
return new ArrayList(map.values());
}
}
6.同构字符串（205-易）
题目描述：如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序！。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例：
输入：s = "egg", t = "add"
输出：true
输入：s = "foo", t = "bar"
输出：false
思路：本题映射的关键是每个字符只能映射到一个字符（单映射，即s通过映射可以得到t），且映射位置不能错。解决方案：
常规解法：建立两个hashmap进行映射，如示例中，t 中的字符 a 和 r 虽然有唯一的映射 o，但对于 s 中的字符 o来说其存在两个映射 {a,r}，故不满足条件。但这种方法效率比较低。
记录一个字符串上次出现的位置，如果两个字符串中字符上次出现的位置不一致，一定不是同构；否则，更新该字符上次出现的位置。
代码：
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s2t = new HashMap<Character, Character>();
Map<Character, Character> t2s = new HashMap<Character, Character>();
int len = s.length();
for (int i = 0; i < len; ++i) {
char x = s.charAt(i), y = t.charAt(i);
if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
return false;
}
s2t.put(x, y);
t2s.put(y, x);
}
return true;
}
public boolean isIsomorphic(String s, String t) {
// 记录两个字符串每个字符上一次出现的位置（一共256个字符）
int[] preIndexOfS = new int[256];
int[] preIndexOfT = new int[256];
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i), tc = t.charAt(i);
if (preIndexOfS[sc] != preIndexOfT[tc]) {
return false;
}
// 字符相同，更新位置
preIndexOfS[sc] = i + 1;
preIndexOfT[tc] = i + 1;
}
return true;
}
7.单词规律（290-易）
题目描述：给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例：
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
思路：基本思路与上题相同，创建两个hash表，建立双向映射（字符串和字符之间的映射）。注意：字符串的比较用equals，String对equals进行了重写，实际是比较的内容！
代码：
public boolean wordPattern(String pattern, String s) {
HashMap<Character, String> map1 = new HashMap<>();
HashMap<String, Character> map2 = new HashMap<>();
String[] ss = s.split(" ");
if (pattern.length() != ss.length) {
return false;
}
int i = 0;
for (char ch : pattern.toCharArray()) {
if (map1.containsKey(ch) && !map1.get(ch).equals(ss[i]) ||
map2.containsKey(ss[i]) && !map2.get(ss[i]).equals(ch)) {
return false;
}
map1.put(ch, ss[i]);
map2.put(ss[i], ch);
i++;
}
return true;
}
