Intermediate Exercism • go

Anagram

Challenge Overview

Given a word and a list of possible anagrams, select the correct sublist.

Introduction

At a garage sale, you find a lovely vintage typewriter at a bargain price! Excitedly, you rush home, insert a sheet of paper, and start typing away. However, your excitement wanes when you examine the output: all words are garbled! For example, it prints “stop” instead of “post” and “least” instead of “stale.” Carefully, you try again, but now it prints “spot” and “slate.” After some experimentation, you find there is a random delay before each letter is printed, which messes up the order. You now understand why they sold it for so little money!

You realize this quirk allows you to generate anagrams, which are words formed by rearranging the letters of another word. Pleased with your finding, you spend the rest of the day generating hundreds of anagrams.

Instructions

Given a target word and one or more candidate words, your task is to find the candidates that are anagrams of the target.

An anagram is a rearrangement of letters to form a new word: for example "owns" is an anagram of "snow". A word is not its own anagram: for example, "stop" is not an anagram of "stop".

The target word and candidate words are made up of one or more ASCII alphabetic characters (A-Z and a-z). Lowercase and uppercase characters are equivalent: for example, "PoTS" is an anagram of "sTOp", but "StoP" is not an anagram of "sTOp". The words you need to find should be taken from the candidate words, using the same letter case.

Given the target "stone" and the candidate words "stone", "tones", "banana", "tons", "notes", and "Seton", the anagram words you need to find are "tones", "notes", and "Seton".

Dig Deeper

Case-insensitive Sorting

// Package anagram contains a solution to the anagram Exercism exercise.
package anagram

import (
	"sort"
	"strings"
)

// Detect determines which words in candidates are anagrams of the subject.
func Detect(subject string, candidates []string) []string {
	anagrams := make([]string, 0)

	subject = strings.ToLower(subject)

	for _, candidate := range candidates {
		c := strings.ToLower(candidate)

		if isAnagram(subject, c) {
			anagrams = append(anagrams, candidate)
		}
	}

	return anagrams
}

// isAnagram determines whether a and b are anagrams of each other.
func isAnagram(a, b string) bool {
	return a != b && sortString(a) == sortString(b)
}

// sortString sorts a string lexicographically in non-decreasing order.
func sortString(s string) string {
	chars := strings.Split(s, "")
	sort.Strings(chars)
	return strings.Join(chars, "")
}

This approach normalizes both strings to lowercase, sorts them, and compares the resulting sorted strings to determine if they are anagrams.

The strings.ToLower function is used to convert the strings into their lowercase form. This normalizes the strings so that the solution is case-insensitive (e.g., foo and OOF normalize to foo and oof). At this point if the two strings normalize to the same string, they cannot be anagrams since a word cannot be an anagram of itself.

The normalized strings are then sorted using the sort package. It doesn’t matter if the strings are sorted in non-decreasing or non-increasing order as long as both strings are sorted in the same way. Sorting the strings allows us to determine if the strings are anagrams (e.g., foo and oof sort to foo and foo). In Go, sorting operates on slices, not strings, so the string is first split into a slice using strings.Split, sorted using sort.Strings, and then joined back into a string using strings.Join.

Now that the strings are normalized and sorted, they can be compared directly to determine if they are anagrams. If the strings are the same, they are anagrams. Otherwise, they are not anagrams.

This approach separates the sorting and anagram checking logic into their own functions for readability. That way, the Detect function can focus on iterating over the candidates and building the resulting slice of anagrams.

Frequency Counter

// Package anagram contains a solution to the anagram Exercism exercise.
package anagram

import (
	"strings"
	"unicode"
)

// Detect determines which words in cases are anagrams of the subject,
// ignoring words that are equal to subject (case-insensitive).
func Detect(subject string, cases []string) []string {
	anagrams := make([]string, 0)

	for _, word := range cases {
		if isAnagram(subject, word) {
			anagrams = append(anagrams, word)
		}
	}

	return anagrams
}

// isAnagram determines whether a and b are anagrams of each other.
func isAnagram(a, b string) bool {
	if strings.ToLower(a) == strings.ToLower(b) {
		return false
	}

	freqCounter := make(map[rune]int)

	for _, r := range a {
		r = unicode.ToLower(r)
		freqCounter[r]++
	}

	for _, r := range b {
		r = unicode.ToLower(r)

		if _, ok := freqCounter[r]; !ok {
			return false
		}

		freqCounter[r]--

		if freqCounter[r] == 0 {
			delete(freqCounter, r)
		}
	}

	return len(freqCounter) == 0
}

This approach utilizes a frequency counter to determine if the strings are anagrams of one another.

The strings.ToLower function is used to convert the strings into their lowercase form where they are then checked for equality. Two strings that are equal after converting to lowercase are not anagrams since they are the same string.

A hash map of type map[rune]int is initialized as the frequency counter. The first string is iterated over and the frequency counter is updated to hold the number of occurances of each character in the string. Before a character is counted in the frequency counter, it’s converted to lowercase to account for case-insensitive strings that should be anagrams (e.g., foo and OOF).

The second string is then iterated over and the frequency counter is checked to see if the lowercase version of the character exists in the hash map. If it does not then the strings cannot possibly be anagrams of one another and the implementation returns early. Otherwise, the number of occurances of the current character is decremented and, if the count of that character reaches 0, the entry is removed from the hash map.

After iterating through both strings and updating the frequency counter the two strings are anagrams if and only if the frequency counter is empty. That is, all of the characters that were counted in the first string have been accounted for when iterating through the second string. If the second string contained a charater that the first string did not, then the implementation would return early as described above. If the second string contained extra characters or different characters than the first string then we’d have a non-empty hash map left over at the end signifying a difference between the two strings.

This approach separates the anagram checking logic into its own function for readability. That way, the Detect function can focus on iterating over the candidates and building the resulting slice of anagrams.

Source: Exercism go/anagram