[LC] 79. Word Search

[seungriyou]

https://leetcode.com/problems/word-search/

Approach

• backtracking으로 접근했다.

  visited 2D array를 만들어도 좋고, visited를 set()으로 관리해도 좋고, board에 in-place로 값을 변경하면서 해도 좋다. 하지만 주어진 argument에 in-place로 바꾸는 건 지양하라는 글을 봐서 visited 2D array를 추가하고, SC를 약간 손해봤다.

  def backtrack(r, c, idx):
      # base condition
      if idx == len(word):
          return True
  
      # (1) 범위를 벗어나거나, (2) 이미 방문했거나, (3) word[i]와 같은 문자가 아니라면 false
      if not (0 <= r < m and 0 <= c < n) or visited[r][c] or board[r][c] != word[idx]:
          return False
  
      visited[r][c] = True
  
      if (
          backtrack(r - 1, c, idx + 1) or
          backtrack(r + 1, c, idx + 1) or
          backtrack(r, c - 1, idx + 1) or
          backtrack(r, c + 1, idx + 1)
      ):
          return True
  
      visited[r][c] = False
  
      return False      

• early stopping을 할 수 있다. word를 구성하고 있는 글자 종류가 board를 구성하고 있는 글자 종류에 포함되어야 가능하므로, 이를 사전에 set()의 .difference 메서드를 이용해서 확인했다. 이렇게 하면 runtime이 3106ms에서 486ms으로 대폭 감소한다!

  if set(word).difference(set(c for row in board for c in row)):
      return False

[!note] BFS는 왜 안 됐을까...? edge case를 못 잡은 것 같은데, BFS로 TLE 안 나게 풀 수 있을까?

Complexity

ref: https://leetcode.com/problems/word-search/solutions/747144/python-dfs-backtracking-solution-explained

• Time: O(m*n*3^k) (m = board의 row 수, n = board의 col 수, k = word의 길이)

  board의 각 cell에서 3 방향(뒤로는 못 감!)을 탐색해야 하기 때문임. 하지만 실제로는 훨씬 적게 걸릴 것임.

• Space: O(m*n) (w/ visited) / O(k) (w/o visited, just recursion stack)