arcbjorn

# thoughtbook

Tuesday, December 20, 2022

# Valid anagram

Leetcode 242 problem.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

## Go

• Time complexity: $O(n)$ - n is a length of a string
• Auxiliary space: $O(1)$ - constant amount of space

#### Byte comparison solution:

func isAnagram(s string, t string) bool {
if len(s)!=len(t) {
return false
}

sourceArray := []byte(s)
// descending sort
sort.Slice(sourceArray, func(i, j int) bool {
return sourceArray[i] < sourceArray[j]
})

// descending sort
targetArray := []byte(t)
sort.Slice(targetArray, func(i, j int) bool {
return targetArray[i] < targetArray[j]
})

return bytes.Equal(sourceArray,targetArray)
}

#### Character frequency solution:

import "strings"

func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}

for _, rune := range s {
frequencyS := strings.Count(s, string(rune))
frequencyT := strings.Count(t, string(rune))

if (frequencyS != frequencyT) {
return false
}
}

return true
}

#### Hash table solution:

func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}

sourceMap := make(map[rune]int)
targetMap := make(map[rune]int)

for _, char := range s {
sourceMap[char]++
}

for _, char := range t {
targetMap[char]++
}

for char, sourceCount := range sourceMap {
if targetCount, exists := targetMap[letter]; !exists || sourceCount != targetCount {
return false
}
}

return true
}