Sözcük Araması II: Trie + Izgarada Geri İzleme
Tüm hedef sözcükleri bir trie’a ekleyin ve tüm geçerli sözcükleri aynı anda bulmak için 2B tahta üzerinde O(m × n × 4^L) sürede DFS geri izlemesi çalıştırın.
Sözcük Araması II: Trie + Izgarada Geri İzleme, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Kelime Arama II Problemi
Kelime Arama II (LeetCode 212): m × n boyutunda karakterlerden oluşan bir tahta ve bir kelime listesi verildiğinde, yatay veya dikey olarak ardışık komşu hücrelerden oluşturulabilen tüm kelimeleri bulun; her hücre yalnızca bir kez kullanılabilir. Bu, Kelime Arama I'den (tek kelime) daha zordur; çünkü tüm eşleşen kelimeleri aynı anda bulmamız gerekir. Her kelime için Kelime Arama I'i saf bir yaklaşımla çalıştırmak O(W × m × n × 4^L) olur ve bu çok yavaştır.
Neden Trie ve Geri İzleme?
Tüm hedef kelimeleri bir trie içine ekleyip ardından tahta üzerinde DFS ile geri izleme yapmak, tüm kelimeleri aynı anda aramamızı sağlar. Her tahta hücresinde, bu yolun hedef kelimemi yazıp yazmadığını kontrol etmek yerine, bu yolun trie içindeki bir ön ekle eşleşip eşleşmediğini kontrol ederiz. Bir trie ön eki eşleşmediği anda tüm DFS dalını budarız; böylece aynı ön eki paylaşan tüm kelimeler için yinelenen işlerden kaçınırız.
Kelime Listesinden Trie Oluşturma
Tüm kelimeleri bir trie içine ekleyin. Yalnızca bir doğru-yanlış değeri yerine, tamamlanmış kelimeyi yaprak düğümünde (node.word) saklayın. Böylece geri izleme sırasında tam bir eşleşme bulunduğunda, kelimeyi karakter karakter yeniden oluşturmadan hemen sonuçlara ekleyebiliriz.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')Izgarada DFS ile Geri İzleme
Tahtadaki her hücreden bir DFS başlatın. Her adımda: (1) geçerli hücrenin karakterinin geçerli trie düğümünde bir alt düğüm olarak bulunup bulunmadığını kontrol edin; (2) bulunuyorsa hücreyi ziyaret edildi olarak işaretleyin (örneğin onu '#' gibi bir yer tutucuyla değiştirin) ve 4 komşu hücreye özyinelemeli olarak girin; (3) özyinelemeden sonra hücreyi eski hâline getirin (işareti kaldırın). Bir trie düğümünde boş olmayan bir word bulunduğunda, onu sonuçlara ekleyin ve yinelenen sonuçları önlemek için değerini None yapın.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']Karmaşıklık Analizi
Zaman: O(m × n × 4^L); burada L, en uzun kelime uzunluğudur. m×n başlangıç hücresinin her biri için DFS, en fazla 4^L yolu keşfeder. Trie, hiçbir kelime ön ekiyle eşleşmeyen yolları budadığından uygulamada işlem çok daha hızlıdır. Trie oluşturma işlemi, W kelime sayısı olmak üzere O(W × L)'dir. Alan: trie için O(W × L) ve özyineleme yığını derinliği için O(L).
Bulduktan Sonra Yaprak Düğümleri Kaldırarak Budama
Bir kelimeyi bulduktan sonra, alt düğümü yoksa yaprak düğümü trie'den kaldırın; yalnızca kelimeyi boş değer yapmayın. Bu, sonraki DFS çağrılarında ölü dalların yeniden ziyaret edilmesini önler. Bir kelime bulunduktan sonra bir düğümün alt düğümleri boşaldığında, onu üst düğümünün alt düğümler sözlüğünden kaldırın. Özellikle çok sayıda kelime uzun ön ekleri paylaşıyorsa bu iyileştirmenin etkisi büyüktür.
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')Kelimeyi Düğümde Tutmak Neden Daha İyi
Tamamlanmış kelimeyi trie'nin yaprak düğümünde saklamanın (DFS yolundan yeniden oluşturmaya kıyasla) iki avantajı vardır: (1) bir eşleşme bulunduğunda O(L) yol yeniden oluşturma yerine O(1) sürede kelimeyi alma; (2) kelimeyi bulduktan sonra node.word = None yapmak, ayrı bir sonuç kümesine gerek kalmadan temiz ve O(1) maliyetli bir yineleme kaldırma işlemidir. Özellikle Kelime Arama II'de yinelenenleri önlemek önemlidir; çünkü aynı kelime teorik olarak farklı yollarla bulunabilir.
Ziyaret Edilen Hücreleri Yerinde İşaretleme
Ayrı bir visited kümesi kullanmak yerine (bu, her DFS yolu için O(m × n) alan gerektirirdi), karakterlerini '#' gibi bir yer tutucuyla değiştirerek hücreleri yerinde işaretleriz. DFS döndükten sonra özgün karakteri geri yükleriz. Bu teknik: (1) hücre başına O(1) ek alan kullanır; (2) tek bir yol içinde yeniden ziyareti otomatik olarak önler; (3) '#' trie içinde hiçbir zaman bulunmayacağından trie dolaşımını tamamen etkilemez.
Ele Alınması Gereken Sınır Durumları
Önemli sınır durumları: (1) kelime listesindeki yinelenen kelimeler — bunları bir kümede saklayın veya sonuçlardaki yinelemeleri önlemek için node.word = None yöntemini kullanın; (2) tahta boyutlarını aşan çok uzun kelimeler — bunlar oluşturulamaz, ancak DFS komşu hücre kalmadığında bunu doğal olarak ele alır; (3) tek hücreli tahta — yalnızca tek karakterli kelimeler bulunabilir; (4) farklı yollarla bulunabilen aynı kelime — node.word = None yöntemi iki kez sayılmasını önler.
Saf Yaklaşımla Karşılaştırma
Saf yaklaşım: W kelimesinin her biri için Kelime Arama I'i çalıştırmak: O(W × m × n × 4^L). Trie ile W'den bağımsız olarak tüm kelimeler aynı anda aranır: O(m × n × 4^L). 10×10 boyutunda bir tahtada uzunluğu 10 olan W=1000 kelime için saf yaklaşım, trie kullanımından 1000 kat daha yavaştır. Trie, tüm kelimeler arasında maliyeti paylaştıran ortak bir ön ek filtresi görevi görür; bu, asimptotik iyileştirme elde etmek için veri yapısı kullanmanın klasik bir örneğidir.
Eksiksiz Çözüm Özeti
Kelime Arama II için eksiksiz çözüm: kelimelerle bir trie oluşturun ve kelime dizisini yaprakta saklayın. Her tahta hücresi için DFS çalıştırın: geçerli karakterin geçerli trie düğümünde bulunup bulunmadığını kontrol edin, hücreyi '#' olarak işaretleyin, 4 komşu hücreye özyinelemeli olarak girin ve hücreyi geri yükleyin. node.word boş değilse onu sonuçlara ekleyin ve değerini boşaltın. İsteğe bağlı olarak, kullanım sonrasında boş trie dallarını budayın. Sonuç listesini döndürün. Zaman: O(m×n×4^L), Alan: O(W×L) trie + O(L) özyineleme.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resultKısa Değerlendirme
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık konularını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: Kelime Arama II, ortak ön ek budamasıyla aynı anda birden çok kelime aramayı mümkün kılmak için trie kullanır, kelime dizisini trie yaprağında saklamak O(1) sürede kelime almayı ve bulduktan sonra onu None yaparak kolayca yineleme kaldırmayı sağlar ve ziyaret edilen hücreleri '#' ile yerinde işaretlemek, her DFS yolu için gereken O(m×n) ek alandan kaçınır. Böylece, mülakatlarda kullanılan en güçlü dizeye özgü veri yapılarından biri olan Ön Ek Ağaçları ve Dize Algoritmaları kursunu tamamladınız.
Sıkça Sorulan Sorular
“Sözcük Araması II: Trie + Izgarada Geri İzleme” dersi ücretsiz mi?
Evet — “Sözcük Araması II: Trie + Izgarada Geri İzleme” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Sözcük Araması II: Trie + Izgarada Geri İzleme” dersinde ne öğreneceğim?
Tüm hedef sözcükleri bir trie’a ekleyin ve tüm geçerli sözcükleri aynı anda bulmak için 2B tahta üzerinde O(m × n × 4^L) sürede DFS geri izlemesi çalıştırın. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Sözcük Araması II: Trie + Izgarada Geri İzleme” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- TrieNode Sınıfı: Ekleme ve Arama
- Ön Ek Araması ve Şununla Başlar
- Trie’da Joker ve Düzenli İfade Araması
- Sözcük Araması II: Trie + Izgarada Geri İzleme