LeetCodeのPermutation in String解いてみた

始めに

今回からLeetCodeで解いた問題をアプトプットしてみる
正直コーディング問題はかなり苦手。
しかし、昨今のエンジニア採用競争は激化していて、有名テック企業などで働くにはコーディングテストやコーディング面接を突破しなければいけない。

重い腰を上げて頑張ってみる

ちなみにLeetCodeとは実際にテック企業で出題されたコーディング問題を解くことができるサイトです。
AtCorderとかよりもアルゴリズム特化って感じ。
カテゴリ毎にeasyとmediumを中心に解いていく。
使う言語はPythonでやってみる。

あ、あと変なことを言う可能性は大いにあるので容赦なくご指摘お願いします

問題

まずこの問題は数値が格納された配列numsが渡され、配列内に同じ数値が2つ以上あればTrue、無ければFalseを返すプログラムを作ればよい。
解法はいくつかあるがまずは簡単な例から試してみる

解法1

最も簡単なのが一つひとつ確かめていく方法
簡単に思いつく方法だが、最悪の場合計算量O(N2) かかります。
当然、タイムオーバーで通りません。
基本的にLeetCodeでブルートフォースは大体時間オーバーで失敗します...

# 解法1 ブルートフォース
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True

        return False

解法2

続いてがハッシュマップ(ハッシュテーブル)を使って各文字の出現数をカウントしていく方法。
この方法なら最悪の場合でも計算量O(N) で余裕で突破できる。
ちなみに自分は最初にこれが思いついた。
シンプルなので解説は不要かもだけどざっくり説明してみる。

例. nums = [1,2,3,1]
上記を例にすると
1は2回
2は1回
3は1回

ハッシュマップにカウントするとこうなる
hash_map = {1: 2, 2: 1, 3: 1}

nums[i]の値が既にhash_map内に存在してる場合、配列内に同じ数字が2つ以上あるということが証明される。
よってこの時点でTrueを返す。
全て通っても同じ値が出てこなかった場合、必然的にFalseになる訳です。

# 解法2 ハッシュマップ
hash_map = {}
for i in range(len(nums)):
    if hash_map.get(nums[i]) is None:
        hash_map[nums[i]] = 1
    else:
        return True
return False

解法3

ソートしてから隣り合う値が同じの時点でTrueとなる。
コードとしてはとてもシンプルで一番わかりやすい。
一見O(N)で計算できそうですが、前処理にソートしてるのでハッシュマップの方が早い。
全体の計算量としてはO(nlogn)+O(n)になるのですが、Big O記法では最も計算量が増える項を優先するのでO(nlogn)となる。(ちょっと自信ない)

nums.sort()
for i in range(1, len(nums)):
    if nums[i] == nums[i-1]:
        return True
return False

感想

ハッシュマップの基本問題なだけあり、この辺はサクッと解けた。
複数のアルゴリズムを組み合わせたりすると一気に理解が追いつかなくなるから今後もアウトプットを続けていきます。
間違った箇所などあればビシバシご指摘お願いします🙇‍♂️