[leetCode/JS] 79. Word Search

문제 설명

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

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

 

m x n 문자열 그리드 board가 주어지고, 이 board에 word가 있다면 true를 return 한다.
단어는 가로 세로로 붙어있어야하고 한번 사용한 글자 칸은 두 번이상 사용할 수 없다. (중복사용불가)

 

입출력 예

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

 

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

 

 

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

 

 

 

 

Constraints

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

 

 

 

---

 

내 솔루션

• 간단한 문제 이지만 그렇지 않은 나의 DFS 구조.ㅋㅋ
• word별로 dfs() 호출하여 다르면 return 만약에 남은 글자가 없으면 true,
• 다음칸은 direaction 이라는 array로 forEach 돌려서 순회함.
• 빠른 속도를 가진 솔루션들과 비교해도 구조가 딱히 다르지 않지만
• forEach나 cur를 안쓰고 index로 하는 방법으로 한 사람들은 좀 빨랐다.
• 현재 글자칸을 '_' 로 초기화하고 dfs가 끝나고 돌아올 때 다시 복원하는 것이 포인트다.

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  const direction = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  let answer = false;

  const dfs = (i, j, cur) => {
    if(board[i][j] !== cur[0]) return
    if(cur.length === 1){
      answer = true;
      return;
    };

    board[i][j] = '_'; // 중복으로 사용하지 않기 위해 초기화
    direction.forEach(([x, y]) => {
      const next = board[i + x] ? board[i + x][j + y] : false;
      if(next){
        dfs(i + x, j + y, cur.slice(1))
      }
    })
    board[i][j] = cur[0]; // 다음 dfs를 위해 다시 글자로 변경
  }

  for(let i = 0; i < board.length; i++) {
    for(let j = 0; j < board[0].length; j++) {
      dfs(i, j, word)
    }
  }
  return answer;
};

 

감상평

• dfs가 이제 정말 익숙해졌다. 맘에들어.