79. Word Search

문제링크: https://leetcode.com/problems/word-search/

매트릭스에서 목표한 문자열을 연결할 수 있는지 찾는 문제다. 중복된 탐색은 불가능.

Solution

1. DFS with Set

지나온 지역을 row_col형태로 저장해 재방문하지 않도록 한다. DFS를 통해 인접한 지역을 탐색하고 조건이 맞는 경우 true를 반환한다.

Algorithm

• DFS를 통해 현재 지점이 존재하고 word[wordIndex]와 일치하는지 확인한다.
• 가능한 포인트의 경우 ${row}_${col}로 hasBeen을 갱신하고 다음 단어를 탐색한다.
• 단어를 끝까지 탐색하면 true를 반환한다.

var exist = function(board, word) {
  // dfs with stack
  const len = word.length;
  const boardRow = board.length;
  const boardCol = board[0].length;
  const dir = [0, -1, 0, 1, 0];
  
  // is validIdx
  const valid = (row, col, been) => {
    return (row >= 0 && row < boardRow && col >= 0 && col < boardCol && !been.has(row + '_' + col));
  }
  
  
  const dfs = (row, col, wordIdx, hasBeen) => {
    if (wordIdx >= len) return true;
    if (!valid(row, col, hasBeen) || board[row][col] !== word[wordIdx]) return false;
    hasBeen.add(row + '_' + col);
    // hasBeen.add(row + '_' + col);
    for (let i = 0; i < 4; i++) {
      if (dfs(row + dir[i] , col + dir[i + 1], wordIdx + 1, hasBeen)) return true;
    }
    hasBeen.delete(row + '_' + col);
    return false;
  }
  
  for (let i = 0; i < boardRow; i++) {
    for (let j = 0; j < boardCol; j++) {
      if (dfs(i, j, 0, new Set())) return true;
    }
  }
  return false;
};

2. DFS with marking

1번의 방법에선 방문한 지역을 확인하기 위해 Set을 사용했다. 하지만 Set.has()의 시간복잡도는 완벽한O(1)이라 하기 어렵기 때문에 다른 마킹 방법을 시도했다. 방문한 지역을 '*'로 마킹해 재방문하지 않도록 하고 경우의수가 더 없을 경우 다시 원래 값으로 돌려놓아 Backtracking한다.

Algorithm

• DFS를 통해 현재 지점이 존재하고 word[wordIndex]와 일치하는지 확인한다.
• 가능한 포인트의 경우 현재 위치를 '*'로 바꾸고 탐색을 지속한다.
• 단어를 끝까지 탐색하면 true를 반환한다.

var exist = function(board, word) {
  // Bruteforce
  // Change marking: *
  const rowLen = board.length, colLen = board[0].length;
  const dir = [0, -1, 0, 1, 0];
  
  // Check if index is valid
  const isValid = (row, col) => {
    return row >= 0 && row < rowLen && col >= 0 && col < colLen;
  }
  
  // DFS for search
  const dfs = (row, col, wordIdx) => {
    if (wordIdx >= word.length) return true;
    
    if (isValid(row, col) && board[row][col] === word[wordIdx]) {
      // Mark visited point as *
      board[row][col] = '*';
      // Search next points
      for (let i = 0; i < 4; i++) {
        if (dfs(row + dir[i], col + dir[i + 1],wordIdx + 1)) return true;
      }
      // Restore visited point
      board[row][col] = word[wordIdx];
      return false;
    }
  }
  
  // Check all starting point
  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      if (dfs(i, j, 0)) return true;
    }
  }
  return false;
};