LeetCode题练习与总结：有效的字母异位词--242
一、题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
提示:
1 <= s.length, t.length <= 5 * 10^4s和t仅包含小写字母
二、解题思路
- 首先判断两个字符串的长度是否相等，如果不相等，直接返回false。
- 创建一个长度为26的整型数组，用于记录每个字母出现的次数。因为英文字母只有26个，所以可以使用数组下标来代表字母，数组值代表该字母出现的次数。
- 遍历字符串s，对于每个字符，将其在数组中的对应位置加1。
- 遍历字符串t，对于每个字符，将其在数组中的对应位置减1。
- 最后遍历数组，如果数组中所有位置的值都为0，则说明t是s的字母异位词，返回true；否则返回false。
三、具体代码
class Solution {public boolean isAnagram(String s, String t) {// 如果两个字符串长度不相等，直接返回falseif (s.length() != t.length()) {return false;}// 创建一个长度为26的数组，用于记录每个字母出现的次数int[] count = new int[26];// 遍历字符串s，对于每个字符，将其在数组中的对应位置加1for (int i = 0; i < s.length(); i++) {count[s.charAt(i) - 'a']++;}// 遍历字符串t，对于每个字符，将其在数组中的对应位置减1for (int i = 0; i < t.length(); i++) {count[t.charAt(i) - 'a']--;}// 遍历数组，如果数组中所有位置的值都为0，则返回truefor (int i = 0; i < 26; i++) {if (count[i] != 0) {return false;}}return true;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
-
首先判断两个字符串的长度是否相等，这是一个O(1)的操作，因为长度是已知的，不需要遍历字符串。
-
创建一个长度为26的整型数组，这是一个O(1)的操作，因为数组的长度是固定的，与输入字符串的长度无关。
-
遍历字符串s，这是一个O(n)的操作，其中n是字符串s的长度。
-
遍历字符串t，这也是一个O(n)的操作，其中n是字符串t的长度，由于题目条件指出s和t的长度相等，因此这里的n可以看作是相同的。
-
最后遍历整型数组，这是一个O(1)的操作，因为数组的长度是固定的26。
将上述步骤的时间复杂度相加，得到总的时间复杂度为O(n) + O(n) + O(1) = O(n)，其中n是字符串s或t的长度。
2. 空间复杂度
- 整型数组count用于记录每个字母出现的次数，这个数组的大小是固定的26，所以空间复杂度为O(1)。
综上所述，该算法的时间复杂度为O(n)，空间复杂度为O(1)。其中n是输入字符串s或t的长度。
五、总结知识点
-
类定义：
class Solution：定义了一个名为Solution的类。
-
方法定义：
public boolean isAnagram(String s, String t)：定义了一个公共方法isAnagram，它接受两个字符串参数s和t，并返回一个布尔值。
-
数组：
int[] count = new int[26];：创建了一个整型数组count，长度为26，用于记录每个字母出现的次数。
-
字符串操作：
s.length()：获取字符串s的长度。s.charAt(i)：获取字符串s中索引为i的字符。
-
字符与整数的转换：
s.charAt(i) - 'a'：将字符转换为整数，通过减去字符’a’的ASCII值，得到字符在数组中的索引位置。
-
ASCII码：
- 使用ASCII码来处理字符，通过字符与’a’的差值来作为数组的索引。
-
算法思想：
- 计数法：通过计数每个字符出现的次数来判断两个字符串是否是字母异位词。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。