[LeetCode] 79. Word Search

轉自LeetCode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

<Solution>

典型使用 DFS 來解的題目

這邊有個地方可以注意一下

一般的做法是會再用一個 2D matrix 來紀錄是否拜訪過

但這題其實可以直接把原本的字元，替換成 *，來代表拜訪過了（當然是因為本題沒用到*）

這樣不但省空間，而且速度也快很多

code 如下

c++

kotlin