英語の辞書が与えられたときにすべてのアナグラムを見つける

引き続き珠玉のプログラミングの問題をやってみようかと
Goでやってます

過去記事

• 文字列をn個後ろにずらす処理を本気でやる

お題

タイトルの通り
英語の辞書が与えられたときにすべてのアナグラムを見つける

アナグラムは同じ文字を異なる順番で使った単語のこと
例えば、[from, form], [time, item]など

単純なやり方としては
単語を1文字ずつずらして、すべての単語についてマッチするか見ていく

しかし、英単語の総数は100万以上らしく、5文字の単語を検査するのにも

5! * 10^{6} = 1.2 * 10^{8}

1回ごとの比較処理が1μ秒だとしても

10^{8}/回 * 10^{-6}秒/回 = 100秒

かかってしまう

上記例は英単語の総数として出していますが、よく調べたら英辞典は17万ほどの収録だそうです

じゃあ、どうすればいいかが本題

答えとしては同じアナグラムのグループに印をつけるということ
そして、同じ印のついた単語をまとめておけば目的が達成されます。

印のつけかたは、各単語の文字列をアルファベット順に並べ替える
単純ですが効果的ですよね、なるほど。。

そうとわかれば後はデータの持ち方きめればすぐに実装できそうですね
こんな感じでやってみました

playground

package plg

import (
    "fmt"
    "sort"
    "strings"
)

var (
    dummyDict = []string{"from", "time", "item", "form", "off", "test"}
)

func Anagram() {
    // 容量割り当てときたいが目安がわからないので保留
    list := make(map[string][]string)

    for _, word := range dummyDict {
        key := sortStr(word)
        list[key] = append(list[key], word)
    }

    for _, words := range list {
        for _, w := range words {
            fmt.Print(w, " ")
        }
        fmt.Println()
    }
}

func sortStr(k string) string {
    s := strings.Split(k, "")
    sort.Strings(s)

    return strings.Join(s, "")
}

output

from form 
time item 
off 
test 

うん、うまくいってますね

一意のグループを表すキーを作るためにソートを使うっていうのは
知ってないと思いつかないので勉強になりました。