LeetCode Word Search

LeetCode解題之Word Search

原題

在一個二維矩陣中，每個元素都是一個字母，要判斷目標字符串能否由該矩陣中的元素連接而成。所謂連接就是從矩陣中的某一個元素開始，向前後左右不斷前進，但不允許再次經過走過的元素。

注意點：

例子：

輸入:

board = 
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"

輸出: True

解題思路

采用深度優先遍歷的方法，以每一個元素為起點進行查找。在此之前，可以做一個簡單的前置判斷，如果目標字符串中的某一個字母的數目比矩陣中所有該字母的數目還多，那麼肯定是找不到目標字符串的。在進行深度遍歷的時候，如果所有當前的遍歷的位置越界或者與預期的值不等則返回，如果值相等，那麼暫時把當前的值用特殊字符代替，防止繼續遍歷的時候又訪問到訪問過的點。

AC源碼

from collections import defaultdict


class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if self._hasEnoughCharacters(board, word):
            m = len(board)
            n = len(board[0])
            for i in range(m):
                for j in range(n):
                    if self._exist(board, i, j, m, n, word):
                        return True
            return False
        else:
            return False

    def _exist(self, board, i, j, m, n, word):
        if len(word) == 0:
            return True
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[0]:
            return False
        temp = board[i][j]
        board[i][j] = "."
        next_target = word[1:]
        next_result = self._exist(board, i - 1, j, m, n, next_target) \
                      or self._exist(board, i + 1, j, m, n, next_target) \
                      or self._exist(board, i, j - 1, m, n, next_target) \
                      or self._exist(board, i, j + 1, m, n, next_target)
        board[i][j] = temp
        return next_result

    def _hasEnoughCharacters(self, board, word):
        character_counts = defaultdict(int)
        for ch in word:
            character_counts[ch] += 1
        return all(sum(map(lambda line: line.count(ch), board)) >= count for ch, count in character_counts.items())


if __name__ == "__main__":
    assert Solution().exist([
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ], "ABCCED") == True
    assert Solution().exist([
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ], "SEE") == True
    assert Solution().exist([
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ], "ABCB") == False