在一個二維矩陣中,每個元素都是一個字母,要判斷目標字符串能否由該矩陣中的元素連接而成。所謂連接就是從矩陣中的某一個元素開始,向前後左右不斷前進,但不允許再次經過走過的元素。
注意點:
嘗試遍歷周圍元素的時候小心越界例子:
輸入:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED"
輸出: True
采用深度優先遍歷的方法,以每一個元素為起點進行查找。在此之前,可以做一個簡單的前置判斷,如果目標字符串中的某一個字母的數目比矩陣中所有該字母的數目還多,那麼肯定是找不到目標字符串的。在進行深度遍歷的時候,如果所有當前的遍歷的位置越界或者與預期的值不等則返回,如果值相等,那麼暫時把當前的值用特殊字符代替,防止繼續遍歷的時候又訪問到訪問過的點。
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