Leetcode 079 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
- Soruda bize bir matrix veriliyor.Matrixin içerisinde rastgele harfler sıralanmış.
- Bu harfler içerisinde bize verilen kelime sıralı olarak var mı yok mu bulmamız isteniyor.
- Burada rekürsif dfs arama yaparak kelimeyi bulabiliriz.
def exist(self, board: List[List[str]], word: str) -> bool:
ROWS, COLS = len(board), len(board[0])# ilk olarak sütun ve sıra uzunluklarını atadık.
path = set() # bulunduğumuz konumu tutacağımız bir değişken listesi oluşturduk.
def dfs(r, c, i):
if i == len(word): #eğer i kelimenin uzunluğuna ulaştı ise kelimeyi bulduk
return True
if(r < 0 or c < 0 or # tablo dışına çıkarsak
r >=ROWS or c >= COLS or
word[i] != board[r][c] or # bir sonraki harf aradığımız harf değil ise
(r, c) in path): # bu konuma zaten daha önce bulunmuşsak
return False #false dön
path.add((r,c)) #dfs tekrar çağırmadan önce konumu kaydet
res = (dfs(r+1,c,i+1) or #bir sonraki harf için bulunduğumuz konumun sağını solunu yukarısını
dfs(r-1,c,i+1) or #aşağısını kontrol et
dfs(r,c+1,i+1) or
dfs(r,c-1,i+1))
path.remove((r,c)) #bulunduğumuz konumu path den çıkar
return res #sonuç dön
#yukarıdaki dfs fonksiyonu kelimenin harflerini sırası ile bulmak için
#alttaki for döngüleri ile tüm matrixi dolaşalım
for r in range(ROWS):
for c in range(COLS):
if dfs(r,c,0): return True
return False