LeetCode生活3日目

はじめに

neetcodeのroadmapに沿ってやっている。

3つ目のtwo sumみたいな問題は前にやってたから飛ばした。

今日はmediumらしい。

いけるかしら。

Group Anagrams

複数の文字列が要素として入っている配列がある。

各要素についてアナグラムであるものをグルーピングし、結果を配列で返せ。

なおグルーピングしたものについては順不同で良い。

考え方(これはわからん)

どうやるのかしら

配列の配列みたいなことになるらしい

そもそもアナグラムであるか否かは前やったchars.sortの結果が等しいか田舎だから

それをどういうふうに回していくべき？

配列の0番目取得して、select {|str| str.chars.sort

いやちゃうな。

Mapにするか

map用意して、各要素をchars.sortしたものをkeyにその文字列とindexをvalueに入れて

以降はkeyで調べてあればvalueに追加、なければ新規作成みたいな

ほんとかね

やってみるか

# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
    hash = {}
    strs.each_with_index do |str, i|
        sort_str = str.chars.sort.join
        hash[sort_str.to_sym] ||= []
        hash[sort_str.to_sym] << i
    end

    hash.values.map do |value|
        value.map {|i| strs[i]}
    end
end

こんな感じ。計算量はかなり多そうな気がするけど。。

とにかく自力で初めてmediumレベル解けたことを喜びましょう。

解法2

一番早い人のサンプルコードを見てみた。

# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
    map1 = {}
    strs.each do |str|
        s = str.bytes.sort
        map1[s] ||= []
        map1[s] << str
    end
    map1.values
end

なんや、ほぼ同じやんと思った。

がわざわざあんなことしないで良かったのかとも思った。

恥ずかしい。笑

終わりに

初めてmediumレベルが自力で解けた。

嬉しみを感じる。

成長だー