[leetcode] 79. Word Search

문제링크

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

input & output

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

---

Approach #1

1)
Input: 1*1~6*6 array
output: true/false
constraints:
 - mxn array, 1<=m<=6, 1<=n<=6
 - 1<=word.length<=15
edge case:

2)
DS:
Algorithm: backtracking

1) if(word[i]==board[i][j]), board[i][j]의 상하좌우 확인한다. (word[i+1]===board[i][j+1]/board[i+1][j])
2) 상하좌우에있어. 있으면 그자리에서 또 다음단어의 알파벳이랑 그자리의 상하좌우 확인. 
3) 만약에 word[word.length-1] 마지막 알파벳까지 찾았어. 그러면 true리턴.
4) 중간에 상하좌우 봤는데도 다음 알파벳이 없어. 그러면 backtracking. (그 전의 자리로........... ^.^.....)
5) 다 돌았는데도 true를 리턴하지 못했으면 false 리턴.

Solution #1

var exist = function(board, word) {
  //edge case
  if(board.length * board[0].length < word.length) return false;
  
  let w=0;
	for(let i=0; i<board.length; i++){ //time: O(m*n^4)
    for(let j=0; j<board[0].length; j++){
        if(backtracking(board, word, w, i, j)) return true;
    }
  }
  return false;
};

function backtracking(board, word, w, startI, startJ){
  // out of index인지, word[w]와 다른지같은지 확인.
  // 만약에 인덱스가 invalid, word[w]와 다르면 return false;
  if(startI<0 || startI>=board.length || startJ<0 || startJ>=board[0].length || word[w]!==board[startI][startJ]) return false; 
  
  // 최종정답인 경우 if(w===word.length-1), 바로 return true;
  if(w===word.length-1) return true;  
  let curBoard= board[startI][startJ];
  // 본애 처리해줌
  board[startI][startJ]=0;
  
  // 상하좌우 확인
  const res = 
  backtracking(board, word, w+1, startI, startJ+1) || 
  backtracking(board, word, w+1, startI+1, startJ) || 
  backtracking(board, word, w+1, startI, startJ-1) || 
  backtracking(board, word, w+1, startI-1, startJ);
  
  // 보드 복구
  board[startI][startJ]= curBoard;
  return res;
}

Time Complexity

O(M N 3^L)

M=board.length, N=board[0].length, L=word.length
내가 이전에 확인한 방향말고 나머지 3방향을 비교하는데, 그 3방향을 단어의 길이(L)만큼 비교할것이고.
그 비교를 보드판의 크기(M*N)만큼, 계속해서 확인해야하기 때문에.

Space Complexity

space O(L)

L=word.length
보드판의 알파벳과 word를 비교하기 위해 word[]배열을 사용했다. 그렇기에 공간복잡도는 word의 길이만큼(word[]배열의 크기)이 될 것.

---