自助建站网信息发布平台,移动网页设计总结,WordPress瀑布流商店博客,管理系统是什么优质博文#xff1a;IT-BLOG-CN
一、题目
给定两个字符串s和t#xff0c;编写一个函数来判断t是否是s的字母异位词。注意#xff1a;若s和t中每个字符出现的次数都相同#xff0c;则称s和t互为字母异位词。
示例 1: 输入: s anagram, t nagaramIT-BLOG-CN
一、题目
给定两个字符串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 * 104 s和t仅包含小写字母 ::: 进阶: 如果输入字符串包含unicode字符怎么办你能否调整你的解法来应对这种情况 Unicode是为了解决传统字符编码的局限性而产生的方案它为每个语言中的字符规定了一个唯一的二进制编码。而Unicode中可能存在一个字符对应多个字节的问题为了让计算机知道多少字节表示一个字符面向传输的编码方式的UTF−8和UTF−16也随之诞生逐渐广泛使用 二、代码
【1】哈希表 我们用哈希表维护对应字符的频次即可。需要注意Unicode一个字符可能对应多个字节的问题不同语言对于字符串读取处理的方式是不同的。
class Solution {public boolean isAnagram(String s, String t) {if (s null || t null || s.length() ! t.length()) {return false;}// 思想创建1个hashMap存储s的字符为keyvalue为字符的个数最后遍历t对value进行递减如果小于0则为false;MapCharacter,Integer map new HashMap();for (int i 0; i s.length(); i) {map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) 1);}for (int i 0; i t.length(); i) {int count map.getOrDefault(t.charAt(i), 0) - 1;if (count 0) {return false;}map.put(t.charAt(i), count);}return true;}
}时间复杂度 O(n)其中n为s的长度。 空间复杂度 O(S)其中S为字符集大小此处S26。
【2】一维数组 如果不考虑Unicode时字符串只包含26个小写字母因此我们可以维护一个长度为26的一维数组table先遍历记录字符串s中字符出现的频次然后遍历字符串t减去table中对应的频次如果出现table[i]0则说明t包含一个不在s中的额外字符返回false即可。
class Solution {public boolean isAnagram(String s, String t) {if (s null || t null || s.length() ! t.length()) {return false;}// 维护一个长度为26的一维数组并将s字符维护进去int[] arr new int[26];for (int i 0; i s.length(); i) {arr[s.charAt(i) - a];}// 遍历t字符串进行count--for (int i 0; i t.length(); i) {arr[t.charAt(i) - a]--;if (arr[t.charAt(i) - a] 0) {return false;}}return true;}
}时间复杂度 O(n)其中n为s的长度。 空间复杂度 O(S)其中S为字符集大小此处S26。
【3】字符排序 t是s的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串s和t分别排序看排序后的字符串是否相等即可判断。此外如果s和t的长度不同t必然不是s的异位词。
class Solution {public boolean isAnagram(String s, String t) {if (s null || t null || s.length() ! t.length()) {return false;}// 投机法对两个字符串排序后判断是否相等char[] s1 s.toCharArray();char[] t1 t.toCharArray();// 排序Arrays.sort(s1);Arrays.sort(t1);// 判断是否相等return Arrays.equals(s1,t1);}
}时间复杂度 O(nlogn)其中n为s的长度。排序的时间复杂度为O(nlogn)比较两个字符串是否相等时间复杂度为O(n)因此总体时间复杂度为O(nlognn)O(nlogn)。 空间复杂度 O(logn)。排序需要O(logn)的空间复杂度。注意在某些语言比如Java JavaScript中字符串是不可变的因此我们需要额外的O(n)的空间来拷贝字符串。但是我们忽略这一复杂度分析因为这依赖于语言的细节这取决于函数的设计方式例如可以将函数参数类型更改为char[]。
