本文共 1906 字,大约阅读时间需要 6 分钟。
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
说明:
你可以假设字符串只包含小写字母。进阶:
如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?如果之前做过这题《》的话,那么这道题就非常简单了。
方法一:
执行用时 :0 ms,击败了100.00% 的用户 内存消耗 :3 MB, 击败了37.50%的用户方法一是我的起手式,
首先将两个字符串中各个元素出现的次数记录到数组a
和b
中 其次利用反射函数比较两个数组是否一致,一致则返回true
,否则false
func isAnagram1(s string, t string) bool { a := [26]int{ } b := [26]int{ } l := len(s) if len(t) != l { return false } for i := 0; i < l; i = i + 1 { a[s[i]-97]++ b[t[i]-97]++ } return reflect.DeepEqual(a, b)}
方法二:
执行用时 :0 ms, 击败了100.00% 的用户 内存消耗 :3 MB, 击败了37.50%的用户方法一的执行效率为100%,这说明程序结构没问题,现在看看有没有细节可提升呢?
数组a
和b
,长度一样,键名也几乎一致~~那么就让s
和t
所遍历的值一个正增长+1
,一个负增长-1
。 数组a
通过反射方法reflect.DeepEqual()
与[26]int{}
进行比较,如果26
个值全为0
则返回true
结果和方法一没什么区别,我估计原因在于反射比较时仍旧需要创建[26]int{}
来占用内存。
func isAnagram2(s string, t string) bool { a := [26]int{ } if len(s) != len(t) { return false } for i := range s { a[s[i]-97]++ a[t[i]-97]-- } return reflect.DeepEqual(a, [26]int{ })}
方法三:
执行用时 :0 ms, 击败了100.00% 的用户 内存消耗 :3 MB, 击败了62.50%/80.00%/100.00% 的用户如果方法二不使用反射,而使用循环遍历来判断是否为字母异位词的话,是否会减少内存占用呢?
于是~~方法三诞生了,最高记录达到了执行效率100%,内存占用100%
func isAnagram3(s string, t string) bool { // if s==t { // return true // } if len(s) != len(t) { return false } a := [26]int{ } for i, v := range s { a[v-97]++ a[t[i]-97]-- } for _, v := range a { if v != 0 { return false } } return true}
方法四:
执行用时 :8 ms, 击败了59.85% 的用户 内存消耗 :3 MB, 击败了40.00%/37.50%的用户根据方法三,想进一步让内存的占用下来,结果惨败
func isAnagram4(s string, t string) bool { if len(s) != len(t) { return false } a := make(map[byte]int, 26) for i := range s { a[s[i]]++ a[t[i]]-- } for _, v := range a { if v != 0 { return false } } return true}
reflect.DeepEqual()
,用法可以参考《》[3]int{}
,其值相当于[0 0 0]
,因此在方法二中[26]int{}
可与数组a
比较转载地址:http://jtkpi.baihongyu.com/