LeetCode 841. Keys and Rooms - スタックループの各言語での条件判定の違い

841. Keys and Rooms

https://leetcode.com/problems/keys-and-rooms/description/

Approach

スタックを使って深さ優先探索を行う。

ruby

def can_visit_all_rooms(rooms)
    stacks = [0]

    visited_rooms = Array.new(rooms.length, false)
    visited_rooms[0] = true

    while (room = stacks.pop)
      rooms[room].each do |key|
        unless visited_rooms[key]
           visited_rooms[key] = true
           stacks << key
        end
      end
    end
    visited_rooms.all?
end

python

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        stacks = [0]
        visited_rooms = [False] * len(rooms)
        visited_rooms[0] = True
        while stacks:
          room = stacks.pop()
          for key in rooms[room]:
            if not visited_rooms[key]:
              visited_rooms[key] = True
              stacks.append(key)

        return all(visited_rooms)

typescript

function canVisitAllRooms(rooms: number[][]): boolean {
  let visited_rooms: boolean[] = new Array(rooms.length).fill(false)
  let stacks: number[]

  stacks = [0]
  visited_rooms[0] = true

  while(stacks.length > 0){
    const room = stacks.pop()

    for (const key of rooms[room]){
      if (!visited_rooms[key]){
        visited_rooms[key] = true
        stacks.push(key)
      }
    }
  }

  return visited_rooms.every(x => x === true)
};

golang

func canVisitAllRooms(rooms [][]int) bool {
    var stacks = []int{0}
    var visitedRooms = make([]bool, len(rooms))
    visitedRooms[0] = true

    for len(stacks)>0 {
      room := stacks[len(stacks)-1]
      stacks = stacks[:len(stacks)-1]
      
      for _, key := range rooms[room]{
        if !visitedRooms[key] {
          visitedRooms[key] = true
          stacks = append(stacks, key)
        }
      }
    }

    for _, visited := range visitedRooms {
      if !visited { return false }
    }
    return true
}

ポイント

• stacksループの条件の判定について

言語	ループ条件	詳細
Ruby	while (room = stacks.pop)	nilはfalseのため。popがnilを返したときにループを終了
Python	while stacks:	空のリストはfalseのため、リストが空になったらループが終了
TypeScript	while(stacks.length > 0)	配列はオブジェクトのためtrueなので、lengthで要素数が0のときにループ終了
Go	for len(stacks) > 0	データ構造に真偽値の概念がないため、len関数で要素数が0のときにループ終了

参考

• golangで、if文に配列を指定するとコンパイルエラーになる。

import "fmt"

func main() {
	var slices []int

	// コンパイルエラーになる
	// ./prog.go:11:5: non-boolean condition in if statement
	if slices {
		fmt.Println("Hello, 世界")
	}
}