LeetCode挑戦日記：Day42

はじめに

最近、業務で実装する時間よりも資料作成やレビューをする時間が多くなってきました。
このままでは自身のコーディング能力が落ちそうで怖いので、LeetCodeを始めてみました。

自身の学習の記録 & LeetCodeに興味のある人が挑戦しやすいように、記事に残していきます。
このような競技プログラミングをした経験がないので、ひよってEasyからやっていきます...

[Medium] 841. Keys and Rooms

0からn-1までラベル付けされたn部屋があり、部屋0を除いてすべての部屋はロックされています。
あなたの目標はすべての部屋を訪れることです。
しかし、鍵がないとロックされた部屋に入ることはできません。

部屋を訪れると、一連の異なる鍵を見つけることがあります。
各鍵には数字が付いており、それがどの部屋を開けるかを示しています。
これらの鍵をすべて持って他の部屋を開けることができます。

配列roomsが与えられたとき、rooms[i]は部屋iを訪れたときに見つける鍵のセットを表します。
すべての部屋を訪れることができる場合はtrueを、そうでない場合はfalseを返します。

素直に解いてみる

考え方

1. 訪れた部屋を保存する配列を作成し、再帰関数を使って見つけた鍵の部屋を順番に訪れていく
2. 全ての部屋を訪れていたらtrueを返す

コーディング

function canVisitAllRooms(rooms: number[][]): boolean {
    const visitedRoom = new Array(rooms.length).fill(false);

    const func = (roomNumber: number): void => {
        if (visitedRoom[roomNumber]) { return; }
        visitedRoom[roomNumber] = true;

        rooms[roomNumber].forEach((key: number) => {
            func(key);
        });
    }
    func(0);

    return visitedRoom.indexOf(false) === -1;
};

結果

Runtime：49ms
Beats 96.94%

Memory：52.08MB
Beats 65.14%