[LeetCode] Word Search

문제

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.

Example:

board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE", return true. Given word = "ABCB", return false.

 

Approach

DFS로 단어를 찾아나갔는데 이전에 방문했던 좌표는 다시 방문하면 안되므로 visited 행렬을 따로 만들어서 관리했더니

메모리 초과 에러가 났다.

그래서 visited 행렬대신 이미 방문한 좌표는 글자를 NULL로 만들어 다시 방문하지 않게 만들고

탐색 후 다시 복구하는 방식으로 했더니 메모리 초과 에러를 피할 수 있었다.

다른 방법들도 보니까 대부분 대동소이 하고 자잘한 최적화 방식으로 속도 차이가 나는듯 하다

나는 60ms까지 줄였음(54.02%)

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_WordSearch.cpp

chi3236/algorithm