[リートコード] 0079. ワードサーチ

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

与えられた xn 文字のグリッド ボード そして文字列 言葉、戻る 真実 もし 言葉 グリッド内に存在する.

単語は、水平または垂直に隣接するセルの文字から構成されます。同じ文字セルを複数回使用することはできません。

例 1:

入力： ボード = [["A","B","C","E"],["S","F","C","S"],["A","D","E ","E"]]、単語 = "ABCCED"
出力： 真実

例 2:

入力： ボード = [["A","B","C","E"],["S","F","C","S"],["A","D","E ","E"]]、単語 = "SEE"
出力： 真実

例 3:

入力： ボード = [["A","B","C","E"],["S","F","C","S"],["A","D","E ","E"]]、単語 = "ABCB"
出力： 間違い

制約:

m == ボードの長さ
n = ボード[i].長さ
1 <= m、n <= 6
1 <= 単語の長さ <= 15
ボード そして 言葉 英語の小文字と大文字のみで構成されます。

フォローアップ： 検索プルーニングを使用して、より大きなサイズでソリューションを高速化できますか？ ボード?

パイソン

				
					# 時間計算量: O(c*3^l) # 空間計算量: O(l) from entering list class ソリューション: def existing(self, board: List[List[str]], word: str) -> bool: def backtrack(suffix: str, r: int, c: int): if len(suffix) == 0: (0 <= r < ROW かつ 0 <= c < COL) または suffix[0] でない場合は True を返します。 = board[r][c]: False を返す 結果 = False originalChar = board[r][c] board[r][c] = "#" for dr,dc in ([1,0],[0,1 ],[-1,0],[0,-1]): result = backtrack(suffix[1:], r+dr, c+dc) 結果の場合: break board[r][c] = originalChar 結果を返すROW = len(board) COL = len(board[0]) 行が範囲(ROW)内にある場合: 列が範囲(COL)内にある場合: バックトラック(word, row, col): Trueを返す Falseを返す board = [[" ["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E" ]] word = "ABCCED" print(Solution().exist(board, word))

パイソン

関連記事