242.有效的字母异位词
给定两个字符串
s和t，编写一个函数来判断t是否是s的字母异位词
。示例 1:
输入: s = "anagram", t = "nagaram" 输出: true示例 2:
输入: s = "rat", t = "car" 输出: false提示:
1 <= s.length, t.length <= 5 * 104s和t仅包含小写字母进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
原理
字母异位词定义：
- 字母异位词（Anagram）是指两个字符串中，字符的种类和每个字符的出现次数完全相同，但字符的顺序可以不同。
思路：
- 首先，字母异位词的核心在于判断两个字符串的字符集合是否完全相同。因此，我们可以通过统计两个字符串中每个字符的出现次数来比较它们。
步骤：
- 创建两个数组
mapS和mapT：这两个数组的长度固定为 26（因为只有 26 个小写字母）。数组mapS用于记录字符串s中每个字符的出现次数，数组mapT用于记录字符串t中每个字符的出现次数。- 遍历字符串
s和t：通过字符的 ASCII 值来定位字符在数组中的位置，然后更新数组中的对应位置。
- 例如，字符
'a'对应的索引是s.charAt(j) - 'a'，即0，字符'b'对应的索引是1，依此类推。- 比较两个数组
mapS和mapT：最终，我们遍历这两个数组，逐个位置进行比较。如果某个位置的字符频次不相同，则返回false，表示这两个字符串不是字母异位词。如果所有位置的频次都相同，则返回true。时间复杂度：
- 遍历两个字符串的时间复杂度为 O(n)，其中
n是字符串的长度。- 遍历两个数组
mapS和mapT的时间复杂度是 O(26)，即常数时间。- 因此，总时间复杂度为 O(n)，其中
n是字符串的长度。空间复杂度：
- 我们只使用了两个固定大小的数组
mapS和mapT，它们的空间复杂度是 O(1)（因为它们的大小是常数 26）。- 总的空间复杂度是 O(1)。
进阶：处理 Unicode 字符
- 如果输入字符串包含 Unicode 字符（不仅限于小写字母），你可以考虑使用一个哈希表（如
HashMap）来存储字符的频次，而不是使用固定大小的数组。- 你可以将字符作为键，字符的出现次数作为值。这样可以处理所有类型的字符，而不仅限于小写字母。
代码
class Solution {
public boolean isAnagram(String s, String t) {
// 创建两个数组，用来存储字符串s和t中各个字符出现的次数
int[] mapS = new int[26]; // mapS 用于存储字符串s的字符频次
int[] mapT = new int[26]; // mapT 用于存储字符串t的字符频次
// 遍历字符串s，更新mapS中各个字符的频次
for (int j = 0; j < s.length(); j++) {
mapS[s.charAt(j) - 'a']++; // 根据字符的ASCII值减去'a'来确定数组的索引
}
// 遍历字符串t，更新mapT中各个字符的频次
for (int j = 0; j < t.length(); j++) {
mapT[t.charAt(j) - 'a']++; // 同上，更新mapT数组
}
// 比较mapS和mapT数组的值，检查两个字符串的字符频次是否完全相同
for (int j = 0; j < 26; j++) {
if (mapS[j] != mapT[j]) { // 如果在某个位置上的频次不同，返回false
return false;
}
}
// 如果所有频次都相同，则返回true，表示t是s的字母异位词
return true;
}
}
38.赎金信
给你两个字符串：
ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。如果可以，返回
true；否则返回false。
magazine中的每个字符只能在ransomNote中使用一次。示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true提示：
1 <= ransomNote.length, magazine.length <= 105ransomNote和magazine由小写英文字母组成
原理
该问题的目标是判断
ransomNote中的每个字符是否都能从magazine中找出对应字符，且每个字符在magazine中只能使用一次。步骤：
字符计数：
- 由于题目限制字符串只包含小写字母，我们可以用一个长度为 26 的数组
mapM来记录magazine中每个字母的出现次数。magazine中的每个字符通过magazine.charAt(i) - 'a'转换为数组索引，从而更新该字符的计数。判断是否可以构建
ransomNote：
- 遍历
ransomNote中的每个字符，并从mapM中减去对应字符的计数，表示我们“使用”了magazine中的一个字符。- 如果在这个过程中，某个字符的计数变为负数，说明
magazine中的字符数量不足，无法满足ransomNote中该字符的需求，因此返回false。最终判断：
- 如果遍历完
ransomNote后，没有出现负数的情况，说明magazine中有足够的字符来构建ransomNote，返回true。时间复杂度：
- 统计
magazine字符的频次需要遍历一次magazine，时间复杂度为 O(m)，其中 m 是magazine的长度。- 遍历
ransomNote来检查字符计数需要遍历一次ransomNote，时间复杂度为 O(n)，其中 n 是ransomNote的长度。- 最后，我们遍历 26 个字母来检查是否有负数，时间复杂度为 O(26)，这是一个常数操作。
- 因此，总的时间复杂度为 O(m + n)，其中 m 和 n 分别是
magazine和ransomNote的长度。空间复杂度：
- 使用了一个长度为 26 的数组
mapM来存储字符的频次，空间复杂度是 O(1)，因为数组的大小是常数。- 总的空间复杂度是 O(1)。
代码
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// 创建一个长度为26的数组mapM，用于存储magazine中每个字母的出现次数
int[] mapM = new int[26];
// 遍历magazine，统计每个字符的出现次数
for (int i = 0; i < magazine.length(); i++) {
mapM[magazine.charAt(i) - 'a']++; // 通过字符减去'a'得到字符的索引，更新字符的计数
}
// 遍历ransomNote，尝试从mapM中减去字符的计数
for (int i = 0; i < ransomNote.length(); i++) {
mapM[ransomNote.charAt(i) - 'a']--; // 将ransomNote中的每个字符从magazine中对应字符的计数中减去
}
// 遍历mapM数组，检查是否有任何位置的值为负
for (int i = 0; i < 26; i++) {
if (mapM[i] < 0) { // 如果某个字符的计数小于0，说明magazine中的字符不足以构成ransomNote
return false; // 返回false，表示无法构造ransomNote
}
}
// 如果所有字符的计数都大于或等于0，表示magazine可以构造ransomNote
return true; // 返回true
}
}
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]仅包含小写字母
原理
该问题的目标是找到字符串
s中所有与p是字母异位词的子串的位置。字母异位词是由相同字母组成但顺序不同的字符串，因此我们可以通过字符的频次来判断两个字符串是否为字母异位词。解决思路：
字符频次编码：
- 字母异位词的核心在于它们的字符频次相同。因此，我们为每个字符串（包括
p和s的子串）计算其字符频次并生成一个编码。- 这里使用一个大小为 26 的数组（
code）来存储字符串中每个字符的频次。字符的频次数组最终转化为一个字符串，作为该字符串的“编码”。滑动窗口：
- 对于字符串
s，我们使用滑动窗口技术来获取长度为p.length()的子串。每次滑动一个字符位置，将窗口内的子串进行编码，并与p的编码进行比较。- 如果某个子串的编码与
p的编码相同，说明这个子串与p是字母异位词，将该子串的起始位置记录下来。HashMap 用于存储编码和位置：
- 使用一个
HashMap（anagrams）来存储每个编码对应的子串起始位置的列表。encode()方法将字符串转化为字符频次编码，并将编码作为键存入anagrams。- 对于每个长度为
p.length()的子串，如果它的编码与p的编码相同，就将该子串的起始位置加入anagrams中。返回结果：
- 在遍历
s后，返回p的编码对应的所有子串的起始位置列表。时间复杂度：
- 计算字符串
p的编码需要 O(m)，其中m是p的长度。- 遍历字符串
s时，我们每次从s中提取长度为m的子串，并计算它的编码。每次计算编码的时间复杂度是 O(m)。- 因此，总的时间复杂度为 O(n * m)，其中
n是s的长度，m是p的长度。空间复杂度：
- 用于存储字符频次的数组
code的大小为常数 26，因此空间复杂度是 O(1)。- 使用
HashMap存储编码和位置列表，最坏情况下，s中的每个子串都可能有一个不同的编码，所以HashMap的大小为 O(n)，其中n是s的长度。
代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 创建一个 HashMap 来存储每个编码对应的位置列表
HashMap<String, List<Integer>> anagrams = new HashMap<>();
// 如果 s 的长度小于 p 的长度，则不可能有字母异位词，直接返回空列表
if (s.length() < p.length()) {
return new ArrayList<>();
}
// 对字符串 p 进行编码，并将其存储到 anagrams 中，确保编码存在
String p1 = encode(p, p.length());
anagrams.putIfAbsent(p1, new ArrayList<>());
// 遍历字符串 s，检查每个长度为 p.length() 的子串
for (int i = 0; i < s.length() - p.length() + 1; i++) {
// 获取当前子串的编码
String s1 = encode(s.substring(i, i + p.length()), p.length());
// 将当前子串的编码放入 anagrams 中，如果编码不存在就初始化一个空列表
anagrams.putIfAbsent(s1, new ArrayList<>());
// 将当前子串的起始位置加入对应的编码列表中
anagrams.get(s1).add(i);
}
// 返回 p 的编码对应的位置列表
return anagrams.get(p1);
}
// 编码函数：将字符串的字符频次转化为固定大小的字符串（长度为26）
public String encode(String str, int len) {
// 创建一个长度为 26 的字符频次数组
char[] code = new char[26];
// 遍历字符串的每个字符，更新对应字符的频次
for (int i = 0; i < len; i++) {
code[str.charAt(i) - 'a']++;
}
// 将字符频次数组转换为字符串作为编码
return String.valueOf(code);
}
}
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仅包含小写字母
原理
该问题要求我们找到字符串
s中所有与字符串p字母异位词相同的子串的起始索引。字母异位词是指两个字符串含有相同的字符，但字符的顺序不同。可以通过字符频次的方式来判断两个字符串是否是字母异位词。解决思路：
编码转换：
- 字母异位词的核心在于它们的字符频次相同，因此我们可以对字符串
p及s中的每个长度为p.length()的子串计算字符频次，并将其转化为一个“编码”。- 这里使用一个大小为 26 的数组（
code）来记录字符的频次。字符的频次数组最终转化为一个字符串，作为该字符串的“编码”。滑动窗口：
- 我们使用滑动窗口技术来获取字符串
s中所有长度为p.length()的子串。- 每当滑动窗口向右移动时，我们检查当前窗口中的子串是否与
p是字母异位词。通过对该子串进行编码并与p的编码进行比较，判断它们是否相等。- 如果它们的编码相等，说明当前子串是字母异位词，我们将该子串的起始索引记录下来。
使用 HashMap 存储编码和位置：
- 我们使用一个
HashMap（anagrams）来存储每个编码对应的子串起始位置列表。encode()方法将字符串转化为字符频次编码，并将编码作为键存入anagrams。- 对于每个长度为
p.length()的子串，计算其编码并与p的编码进行比较。如果它们相等，说明该子串是p的字母异位词，将该子串的起始位置加入anagrams中。返回结果：
- 最后，我们返回
p的编码对应的所有子串的起始位置列表，即返回所有字母异位词的位置。时间复杂度：
- 对于字符串
s中的每个长度为p.length()的子串，计算其字符频次编码的时间复杂度是 O(m)，其中m是p的长度。- 遍历字符串
s时，我们每次滑动窗口并计算子串的编码，这样的操作共进行n - m + 1次，其中n是s的长度。- 因此，总的时间复杂度是 O(n * m)，其中
n是s的长度，m是p的长度。空间复杂度：
- 用于存储字符频次的数组
code的大小为常数 26，因此空间复杂度是 O(1)。- 使用
HashMap存储编码和位置列表，最坏情况下，s中的每个子串都可能有一个不同的编码，所以HashMap的大小为 O(n)，其中n是s的长度。
代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 创建一个 HashMap 用于存储编码与对应的子串起始索引
HashMap<String, List<Integer>> anagrams = new HashMap<>();
// 如果 s 的长度小于 p 的长度，无法找到字母异位词，直接返回空列表
if (s.length() < p.length()) {
return new ArrayList<>();
}
// 对字符串 p 进行编码，生成一个固定的字符频次表示
String p1 = encode(p, p.length());
// 确保 p 的编码在 anagrams 中存在
anagrams.putIfAbsent(p1, new ArrayList<>());
// 遍历字符串 s，获取每个长度为 p.length() 的子串
for (int i = 0; i < s.length() - p.length() + 1; i++) {
// 获取当前子串的编码
String s1 = encode(s.substring(i, i + p.length()), p.length());
// 确保当前子串编码在 anagrams 中存在
anagrams.putIfAbsent(s1, new ArrayList<>());
// 将当前子串的起始位置添加到对应编码的列表中
anagrams.get(s1).add(i);
}
// 返回 p 的编码对应的子串起始位置列表
return anagrams.get(p1);
}
// 编码函数：将字符串转换为一个字符频率数组的字符串表示
public String encode(String str, int len) {
// 创建一个长度为 26 的数组，用于记录字符的频次
char[] code = new char[26];
// 遍历字符串中的每个字符，更新字符的频次
for (int i = 0; i < len; i++) {
code[str.charAt(i) - 'a']++;
}
// 将字符频次数组转换为字符串并返回
return String.valueOf(code);
}
}
这题其实不用hash，能更好的解决，其实是滑动窗口的思想，滑动窗口能把时间复杂度降低到o(n)
原理
该问题要求我们在字符串
s中找到所有的字母异位词子串的起始索引。字母异位词是由相同字母组成，但字母的顺序可以不同。可以通过字符的频次来判断两个字符串是否是字母异位词。解决思路：
字符频次差异：
- 我们使用一个长度为 26 的数组
code来记录s和p中各个字母的频次差异。通过在遍历过程中对字符频次的增减，来判断当前窗口内的子串是否与p是字母异位词。滑动窗口：
- 我们使用滑动窗口技术来遍历字符串
s中的每个长度为p.length()的子串。- 对于每一个字符，更新对应频次数组中的计数，并检查当前窗口中的字符频次是否与
p完全匹配。- 如果字符频次数组中的所有值均为0，说明当前子串与
p是字母异位词，并将其起始位置记录下来。更新字符频次：
- 每次滑动窗口时，当前窗口右端字符的频次会被减1，表示该字符被当前窗口包含。
- 然后，检查当前窗口是否是字母异位词，如果是，就记录下当前窗口的起始位置。
- 滑动窗口后，移出窗口左端字符时，我们需要恢复该字符的频次。
判断字母异位词：
- 通过
IsAnagrams方法检查字符频次数组是否全为0，如果是，说明该子串是字母异位词。时间复杂度：
- 遍历字符串
s的时间复杂度是 O(n)，其中n是字符串s的长度。- 每次遍历时，我们需要检查一个长度为 26 的字符频次数组，
IsAnagrams方法的时间复杂度是 O(26) ≈ O(1)，因此可以认为是常数时间操作。- 总的时间复杂度是 O(n)，其中
n是字符串s的长度。空间复杂度：
- 使用一个大小为 26 的数组
code来存储字符频次，因此空间复杂度是 O(1)，因为数组大小固定。- 使用一个列表
anagrams存储所有字母异位词的起始位置，空间复杂度为 O(k)，其中k是找到的字母异位词的数量。- 因此，总的空间复杂度是 O(k)。
代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 创建一个长度为26的数组用于存储字符频次差异
int[] code = new int[26];
// 创建一个列表用于存储结果：所有字母异位词的起始索引
List<Integer> anagrams = new ArrayList<>();
// 遍历字符串 p，更新字符频次（将 p 中的每个字符计数加1）
for (int i = 0; i < p.length(); i++) {
code[p.charAt(i) - 'a']++; // 更新 p 中字符的频次
}
// 遍历字符串 s，检查每个长度为 p.length() 的子串是否是字母异位词
for (int i = 0; i < s.length(); i++) {
// 更新当前字符的频次（s 中的字符频次减1）
code[s.charAt(i) - 'a']--;
// 如果当前字符频次数组符合字母异位词条件（即所有字符的频次均为0），
// 说明当前子串是 p 的字母异位词，将其起始位置加入结果列表
if (IsAnagrams(code) == true) {
anagrams.add(i + 1 - p.length()); // 记录当前子串的起始索引
}
// 如果 i+1-p.length() >= 0，则恢复上一个字符的频次（滑动窗口移动）
if (i + 1 - p.length() >= 0) {
code[s.charAt(i + 1 - p.length()) - 'a']++;
}
}
return anagrams; // 返回所有字母异位词的起始索引列表
}
// 判断当前字符频次数组是否为字母异位词的条件：如果所有元素为0，则是字母异位词
public boolean IsAnagrams(int[] array) {
// 遍历频次数组，检查是否每个字符的频次均为0
for (int i = 0; i < 26; i++) {
if (array[i] != 0) {
return false; // 如果有任何一个字符的频次不为0，说明不是字母异位词
}
}
return true; // 所有字符的频次为0，说明是字母异位词
}
}