79.Word Search

tags: Medium,Array,Backtracking,Matrix

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.

範例

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

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

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.

解答

Python

小羊解完不貼我先貼

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        row_len = len(board[0])
        col_len = len(board)
        word_len = len(word)
        
        # can add conditions before searching
        # trivial: word length must be less than board size
        # big improve: count and compare each character
        
        # Za
        def worudoSearch(row, col, word_idx):
            if word_idx >= word_len:
                return True
            elif 0 <= row < col_len and 0 <= col < row_len and board[row][col] == word[word_idx]:
                # store and RECOVER visited, credit to Marsgoat
                tmp = board[row][col]
                board[row][col] = ''
                
                if worudoSearch(row+1, col, word_idx+1) or worudoSearch(row, col+1, word_idx+1) \
                or worudoSearch(row-1, col, word_idx+1) or worudoSearch(row, col-1, word_idx+1):
                    return True
                
                board[row][col] = tmp
                
        # loop through
        for row in range(col_len):
            for col in range(row_len):
                if worudoSearch(row, col, 0):
                    return True
        return False

DT Nov 24, 2022

感覺很好玩，我也來貼一下

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        if len(word) > m * n:
            return False
        if not (cnt:=Counter(word)) <= Counter(chain(*board)):
            return False
        if cnt[word[0]] > cnt[word[-1]]:
            word = word[::-1]
        
        def dfs(i, j, s = 0):
            if s == len(word):
                return True
            if 0 <= i < m and 0 <= j < n and board[i][j] == word[s]:
                board[i][j] = '#'
                children = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]
                result = any(dfs(ci, cj, s+1) for ci, cj in children)
                board[i][j] = word[s]
                return result
            return False
        
        return any(dfs(i, j) for i, j in product(range(m), range(n)))

解完後發現很久之前submit過了，之前寫的版本中沒有4~9行的檢查也可以通過，只是會比較慢一點。
Yen-Chi ChenThu, Nov 24, 2022 10:19 PM

凡人Backtracking

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        
        def dfs(x, y, step):
            if x < 0 or x == n or y < 0 or y == m or word[step] != board[y][x]:
                return False
            
            if step == len(word) - 1:
                return True
            
            # Backtracking
            ori = board[y][x]
            board[y][x] = '#'
            found = dfs(x-1, y, step+1) or dfs(x+1, y, step+1) or dfs(x, y-1, step+1) or dfs(x, y+1, step+1)
            board[y][x] = ori
            
            return found
            
        for y in range(m):
            for x in range(n):
                if dfs(x, y, 0):
                    return True
                
        return False

Kobe BryantNov 25, 2022

C++

vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool search(vector<vector<char>>& board, int row, int col, string& word, int index)
{
    if(row < 0 || col < 0 || row == board.size() || col == board[0].size())
        return false;
    if(board[row][col] != word[index])
        return false;
    if(index == word.size()-1)
        return true;
    char orig_c = board[row][col];
    board[row][col] = '#';
    bool res = false;
    for(auto& d : dirs)
        res |= search(board, row+d[0], col+d[1], word, index+1);
    board[row][col] = orig_c;
    return res;
}

bool exist(vector<vector<char>>& board, string word) {
    if(board.size() == 0 || board[0].size() == 0) return false;
    int row_n = board.size(), col_n = board[0].size();
    for(int row = 0; row < row_n; row++)
    {
        for(int col = 0; col < col_n; col++)
            if(search(board, row, col, word, 0))
                return true;
    }
    return false;
}

Time:

$O(M\ast N\ast 4^L)$ 最多走M*N格, 每格最走4個方向, 走字串長度(L)步
Extra Space:

$O(1)$

XD Nov 24, 2022

Javascript

function exist(board, word) {
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] === word[0]) {
        const start = [i, j, 1];
        if (search(board, word, start)) return true;
      }
    }
  }

  return false;
}

function search(board, word, start) {
  const isInBounds = (x, y, xLength, yLength) => x < xLength && x >= 0 && y < yLength && y >= 0;
  const [x, y, step] = start;
  board[x][y] = ''; // 跟大家學習，不用visited了
  if (step === word.length) return true;
  const neighbors = [
    [x + 1, y],
    [x - 1, y],
    [x, y + 1],
    [x, y - 1],
  ];
  for (const [nx, ny] of neighbors) {
    if (!isInBounds(nx, ny, board.length, board[0].length)) continue;
    if (board[nx][ny] === word[step]) {
      if (search(board, word, [nx, ny, step + 1])) return true;
    }
  }
    
  board[x][y] = word[step - 1];

  return false;
}

唐神通靈大師太神啦，只看錯誤case就知道是visited沒有重置，有夠強，學習了。
Marsgoat Dec 1, 2022

Reference

回到題目列表