有效的字母異位詞的golang實現

給定兩個字元串 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)時間複雜度的寫法，時間比上面那個寫法提升了不少

說明:

你可以假設字元串只包含小寫字母