アナグラムを判定する

　問題を確認する

二つの文字がアナグラムかどうかを判定する

思考工程

例えば
listen
silent
はアナグラムです。
文字列の長さが同じかどうかを判定して最初に思い浮かぶのはlistenの最初の文字lをsilentに存在するかどうか判定して、iがsilentにあるかどうか判定して。。。全部の文字がsilentに存在すればアナグラムとなります。
これだとO(n^2)となりもう計算効率が悪くなります

改善

アナグラムとは本質的には同じ文字が同じ文字数あればいいので、各文字数をカウントして両者の文字数のカウントが同じになれば良い。
例えば
listen は l => 1, i => 1, s => 1, t => 1, e => 1, n => 1

silent は s => 1, i => 1, l => 1, e => 1, n => 1, t => 1

となりアナグラムだと判定できます。
listen と strike　はn の数が違うのでアナグラムとはならないです。
ここまで来るとアナグラムはこの方法で解けそうです。

さて計算量はどうなるでしょうか？ 文字数のカウントに必要な計算量が O(N + N)。そこから各文字数のカウントを確認する計算量がO(N) となります。
となって全体ではO(N)となります。最初の計算より効率が良さそうです。
じゃあメモリの使用量はどうなるかというと二つのハッシュマップを用意しないといけないためO(N + N) => O(N) となります。

実装

const isAnagram = (str1, str2) => {
    if(str1.length === str2.length) {
        const {str1Count, str2Count} = countLetter(str1, str2)
        return equalObj(str1Count, str2Count)
    } else {
        return false
    }
}
const equalObj = (obj, obj2) => {
    for(const key in obj) {
        if(obj[key] !== obj2[key]) {
            return false 
        }
    }

    return true
}
const countLetter = (str1, str2) => {
    function count(l, obj) {
        if(obj[l] == null) {
            obj[l] = 1
        } else {
            obj[l] += 1
        }
    }
    let str1Count = {}
    let str2Count = {}

    for(let i = 0; i < str1.length; i++) {
        const s1 = str1[i]
        count(str1[i], str1Count)
        count(str2[i], str2Count)
    }

    return {str1Count, str2Count}
}
isAnagram("listen", "strike"))

となりアナグラムの問題を解くことができます