代码随想录 (programmercarl.com)
这里对哈希表的解读相当到位，多去理解
242.有效的字母异味词
242. 有效的字母异位词
简单
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
class Solution {
public boolean isAnagram(String s, String t) {
// 将字符串s转换为字符数组
char[] sArr = s.toCharArray();
// 对字符数组进行排序
Arrays.sort(sArr);
// 将排序后的字符数组转换回字符串
s = new String(sArr);
// 将字符串t转换为字符数组
char[] tArr = t.toCharArray();
// 对字符数组进行排序
Arrays.sort(tArr);
// 将排序后的字符数组转换回字符串
t = new String(tArr);
// 如果排序后的字符串s和t相等，则返回true，表示它们是字谜词
if(s.equals(t)){
return true;
}
// 否则返回false，表示它们不是字谜词
return false;
}
}
简单思路，转为数组排序
class Solution {
public boolean isAnagram(String s, String t) {
// 创建一个HashMap，用于存储每个字符及其出现的次数
Map
// 如果s和t的长度不相等，则它们不可能是字母异位词，直接返回false
if (s.length() != t.length()) {
return false;
}
// 遍历s中的每个字符，将其添加到map中，并将其值初始化为0
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), 0);
}
// 遍历s中的每个字符，将其在map中的值加1
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
}
// 遍历t中的每个字符，检查它是否在map中存在，如果不存在，则返回false
for (int i = 0; i < t.length(); i++) {
if (!map.containsKey(t.charAt(i))) {
return false;
}
// 如果存在，则将其在map中的值减1
map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
}
// 遍历map中的每个值，如果有任何一个值不为0，则返回false
for (Integer value : map.values()) {
if (value != 0) {
return false;
}
}
// 如果所有字符的出现次数都相等，则返回true
return true;
}
}
我的第一想法是利用哈希表的方式，相较于代码随想录中的解答繁琐。
标准解答中的思路其实是相当于通过数组的index和元素构造了一个key-value，整体思路一致
class Solution {
public boolean isAnagram(String s, String t) {
//共只有26个可能出现的字母
int[] record = new int[26];
//将s字符串中所有的字符存入record中
for (int i = 0; i < s.length(); i++) {
record[s.charAt(i) - 'a']++; // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
}
//减去t字符串中所有字符的数量
for (int i = 0; i < t.length(); i++) {
record[t.charAt(i) - 'a']--;
}
for (int count: record) {
if (count != 0) { // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
return true; // record数组所有元素都为零0，说明字符串s和t是字母异位词
}
}
对于字母异味词这类的题目，重要思路是把字符串转化为数组，排序后字母异味词就会相同
49.字母异位词分组
49. 字母异位词分组
中等
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] 仅包含小写字母
class Solution {
// 定义一个方法，接收一个字符串数组作为参数，返回一个列表的列表
public List
// 创建一个哈希映射，用于存储字符排序后的字符串和对应的原字符串列表
Map
// 遍历输入的字符串数组
for (String str : strs) {
// 将字符串转换为字符数组
char[] array = str.toCharArray();
// 对字符数组进行排序
Arrays.sort(array);
// 将排序后的字符数组转换回字符串，作为哈希映射的键
String key = new String(array);
// 从哈希映射中获取与当前键对应的原字符串列表，如果没有则创建一个新的列表
List
// 将当前字符串添加到原字符串列表中
list.add(str);
// 将原字符串列表放回哈希映射中
map.put(key, list);
}
// 将哈希映射的值（即原字符串列表）转换为列表的列表并返回
return new ArrayList
}
}
438.找到字符串中所有字母异味词
438. 找到字符串中所有字母异位词
已解答
中等
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104s 和 p 仅包含小写字母
自己的思路，沿用了上面字符串化为数组排序的想法
class Solution {
// 定义一个方法，接收两个字符串参数s和p，返回一个整数列表
public List
List
char[] pArray = p.toCharArray(); // 将字符串p转换为字符数组
Arrays.sort(pArray); // 对字符数组进行排序
String pStr = new String(pArray); // 将排序后的字符数组转换回字符串
int first = 0; // 定义一个变量first，表示子串的起始位置
int second = p.length() - 1; // 定义一个变量second，表示子串的结束位置
// 当子串的结束位置小于字符串s的长度时，执行循环
while(second < s.length()){
String son = s.substring(first,second + 1); // 从字符串s中截取子串son
char[] sonArray = son.toCharArray(); // 将子串son转换为字符数组
Arrays.sort(sonArray); // 对字符数组进行排序
String sonStr = new String(sonArray); // 将排序后的字符数组转换回字符串
if(sonStr.equals(pStr)){ // 如果子串son与字符串p相等
result.add(first); // 将子串的起始位置添加到结果列表中
}
first++; // 将子串的起始位置向后移动一位
second++; // 将子串的结束位置向后移动一位
}
return result; // 返回结果列表
}
}
滑动窗口法，固定滑窗大小，数组储存，太精妙了
class Solution {
public List
// 创建一个用于存储结果的列表
List
// 如果字符串s的长度小于字符串p的长度，直接返回空列表
if(s.length() // 创建两个数组，分别用于存储窗口内字符的频率和字符串p中字符的频率 int[] window = new int[26]; int[] pCount = new int[26]; // 遍历字符串p，统计每个字符出现的次数 for (int i = 0; i < p.length(); i++) { pCount[p.charAt(i)-'a']++; } // 定义左右指针，分别表示窗口的起始位置和结束位置 int left = 0, right = 0; // 当右指针没有到达字符串s的末尾时，进行循环 while(right // 将当前字符加入窗口 window[s.charAt(right)-'a']++; // 如果窗口的大小等于字符串p的长度，说明找到了一个符合条件的子串 if(right-left+1==p.length()){ // 判断窗口内的字符频率是否与字符串p中的字符频率相等 if(Arrays.equals(pCount,window)) res.add(left); // 将左指针指向的字符从窗口中移除 window[s.charAt(left)-'a']--; left++; } // 右指针向右移动一位 right++; } // 返回结果列表 return res; } } 文章链接
发表评论