程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Word Search

LeetCode Word Search

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved