有效的字母异位词的golang实现

发布时间：2020-12-16 09:31:19 所属栏目：大数据来源：网络整理

导读：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。输入: s = " anagram " ,t = " nagaram " 输出: true 输入: s = " rat " ,t = " car " 输出: false 说明: 你可以假设字符串只包含小写字母首先看到题目的意思就是说两个字符串的

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

输入: s = "anagram",t = "nagaram"
输出: true
输入: s = "rat",t = "car"
输出: false

说明:

你可以假设字符串只包含小写字母

首先看到题目的意思就是说两个字符串的字母一样，只是位置可以不一样

而且说明也说了，只包含小写字母。

那我们可以通过对两个字符串里面的字符进行排序，如果排序后的两个字符串是一样的，那么就可以说这两个字符串是有效的

// 比较两个排好序的字符串是不是一样
func isAnagram(s string,t string) bool {
    var ss []string
    var ts []string
    for _,c := range s {
        ss = append(ss,string(c))
    }
    for _,c := range t {
        ts = append(ts,string(c))
    }
    sort.Strings(ss)
    sort.Strings(ts)
    return reflect.DeepEqual(ss,ts)
    // return stringSliceEqualBCE(ss,ts)
}

func stringSliceEqualBCE(a,b []string) bool {
    if len(a) != len(b) {
        return false
    }

    if (a == nil) != (b == nil) {
        return false
    }

    b = b[:len(a)]
    for i,v := range a {
        if v != b[i] {
            return false
        }
    }

    return true
}

因为题目说了，字符串只包含小写字母，那我们就可以放心地对字符串进行foreach了

但是这个写法耗时非常严重。

两个for，O(n)
两个排序,O(Nlogn)
乍看起来是一个O(Nlogn)的时间复杂度，但是几个加起来，时间就非常不乐观了

还有另外一种方法就是，使用map把字符串的字符出现个数保存起来

// 用两个字典分别把两个字符串的字符出现个数保存起来
func isAnagram1(s string,t string) bool {
    var sMap = make(map[rune]int)
    var tMap = make(map[rune]int)

    for _,c := range s {
        sMap[c] = sMap[c] + 1
    }
    for _,c := range t {
        tMap[c] = tMap[c] + 1
    }
    return reflect.DeepEqual(sMap,tMap)
}

这个写法是一个O(N)时间复杂度的写法，时间比上面那个写法提升了不少

你可以假设字符串只包含小写字母

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!