Trie’da Joker ve Düzenli İfade Araması
Belirli derinlikteki tüm çocuklara dallanarak '.' joker karakter eşleşmesini destekleyin ve tasarla-ekle-ve-sözcüklerde-ara veri yapısı problemini çözün.
Trie’da Joker ve Düzenli İfade Araması, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. 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.
Joker Karakter Arama Problemi
Standart trie araması tam karakterleri işler. Joker karakter araması, herhangi bir tek karakterle eşleşen özel bir '.' karakteri ekler. Arama sırasında bir '.' ile karşılaştığımızda, belirli bir alt düğümü izlemek yerine tüm alt düğümleri denememiz gerekir; buna dallanma denir. LeetCode 211'deki 'Kelime Veri Yapısı Ekleme ve Arama Tasarımı' probleminin temel fikri budur. Her '.', o düzeydeki alt düğüm sayısı kadar arama yolunu çoğaltır.
Özyinelemeli Joker Karakter Araması
Joker karakter aramasını özyinelemeli bir DFS yardımcı işleviyle uygulayın. Desendeki her karakter için şu işlemi yapın: gerçek bir karakterse belirli alt düğümü izleyin (yoksa False döndürün); '.' ise tüm alt düğümlere özyinelemeli olarak girin ve herhangi biri başarılı olursa True döndürün. Desenin sonuna gelindiğinde node.is_end döndürün.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # FalseDallanma İçin Kısa Devreli Değerlendirme
Bir '.' ile karşılaşıldığında any(dfs(child, i+1) for child in node.children.values()) çağrısını yaparız. any() üreteci kısa devreli çalışır; bir alt düğüm True döndürür döndürmez durur. Böylece gereksiz keşiflerin önüne geçilir. En kötü durumda (tamamı '.' olan bir desende) tüm yolları keşfederiz; karmaşıklık, nokta sayısı k olmak üzere O(26^k) olur. Bu nedenle '....' gibi desenler büyük trie yapılarında maliyetlidir.
Kuyruklarla Özyinelemesiz Joker Karakter Araması
Özyinelemesiz yaklaşım, (node, index) çiftlerinden oluşan bir kuyruk kullanır. (root, 0) ile başlayın. Her çift için, index == len(word) ve node.is_end koşulları sağlanıyorsa True döndürün. Aksi halde geçerli karakteri işleyin: '.' için tüm alt düğümleri kuyruğa ekleyin; gerçek bir karakter için yalnızca eşleşen alt düğümü ekleyin. Bu, temelde trie yolları üzerinde gerçekleştirilen bir BFS işlemidir.
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')Joker Karakter Aramasının Karmaşıklık Analizi
Joker karakter içermeyen bir desen için arama O(m) olur. k joker karakter içeren bir desende en kötü durum O(26^k × m)'dir; bu, joker karakter sayısına göre üstel bir büyümedir. Uygulamada joker karakterler genellikle seyrektir ve trie sığdır; bu nedenle performans kabul edilebilir düzeydedir. Tamamı joker karakterlerden oluşan desenlerde (örneğin uzunluğu k olan tüm kelimelerle eşleşirken) işlem, trie'nin tamamını dolaşmaya dönüşür.
Tek Karakterlik Joker Karakterlerin Ötesinde Düzenli İfade Araması
Tam düzenli ifade desteği (örneğin sıfır veya daha fazla karakterle eşleşen '*') farklı bir işleme gerektirir. '*' herhangi bir son ekle eşleşebildiğinden, onunla karşılaşıldığında geçerli düğümden başlayan tüm trie yollarını denememiz gerekir. Trie içinde gerçek düzenli ifade eşleştirmesi karmaşıktır; genellikle NFA/DFA oluşturmaları için ayrılır. Mülakatlarda tek karakterlik joker karakterler ('.') standart desendir.
Joker Deseni Eşleştirme
'?' (herhangi bir tek karakter) ve '*' (boş dizi de dahil olmak üzere herhangi bir dizi) içeren joker deseni eşleştirmesi DP ile uygulanabilir. Trie içinde uygulanacaksa '?' tek düzeyli dallanmaya ('.' gibi), '*' ise çok düzeyli DFS'ye karşılık gelir. Birleşik DP yaklaşımında dp[i][j], pattern[0..i] ifadesinin string[0..j] ile eşleşmesi durumunda True'dur. Mülakatı yapan kişi genellikle hangi çeşidin uygulanacağını belirtir.
Pratik Uygulama: IP Adresi Yönlendirme
Joker karakterli trie yapıları, '*' karakterinin ön ek joker karakteri olarak davrandığı IP yönlendirme tablolarında kullanılır. Bir yönlendirici '192.168.*' gibi rota ön eklerini saklar ve gelen adresleri bunlarla eşleştirir. En uzun ön ek eşleştirmesi (en özgül rota kazanır), trie'yi mümkün olduğunca derin dolaşarak ve görülen son eşleşmeyi kullanarak uygulanır. Bu, trie ön eki ve joker karakter işlemlerinin gerçek dünyadaki bir uygulamasıdır.
İyileştirme: Ölü Dalların Budanması
Bir trie düğümünün alt düğümü yoksa (yapraksa) ve is_end = False ise, ona ulaşan her arama False döndürür. Joker karakter araması sırasında özyinelemeye geçmeden önce bu çıkmaz düğümleri atlamak, gereksiz çağrıları budayabilir. Her düğümde bir word_count tutmak (alt ağaçtaki toplam kelime sayısı), kalan desen uzunluğu kısıtlarıyla hiçbir kelime eşleşmiyorsa tüm bir alt ağacı atlamamızı sağlar.
Eksiksiz WordDictionary Sınıfı (Mülakata Hazır)
Ekleme ve nokta joker karakteriyle aramayı tek bir sınıfta birleştiren temiz, mülakata hazır bir WordDictionary. Bu, LeetCode 211 için beklenen uygulamanın tam hâlidir. Kısa devreli değerlendirmeye sahip özyinelemeli arama, kısa ve özdür; dallanma mantığını mülakatı yapan kişilere açıkça gösterir.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # FalseKompakt Trie için setdefault Kullanımı
dict.setdefault(key, default), key için bir değer varsa onu döndürür; yoksa default değerini ekler ve döndürür. Ekleme işleminde node.setdefault(c, {}) kullanmak if-else kontrolünü ortadan kaldırır: eksikse alt düğüm sözlüğünü oluşturur ve her iki durumda da onu döndürür. Böylece ekleme işlemi tek satırlık bir dolaşım hâline gelir: for c in word: node = node.setdefault(c, {}). Temiz ve Python tarzı bir kullanımdır.
Kı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: joker karakter '.', eşleşen konumda özyinelemeli DFS kullanarak tüm alt düğümlere dallanmayı gerektirir, üreteçle birlikte any() kullanmak, erken sonlandırma için kısa devreli değerlendirme sağlar ve setdefault, trie'ye eklemeyi kompakt bir tek satır hâline getirir. Sırada, aynı anda birden çok kelime bulmak için trie ile geri izlemeyi birleştirerek Word Search II problemini çözmek var; bu işlem 2B bir tahta üzerinde gerçekleştirilir.
Sıkça Sorulan Sorular
“Trie’da Joker ve Düzenli İfade Araması” dersi ücretsiz mi?
Evet — “Trie’da Joker ve Düzenli İfade Araması” 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.
“Trie’da Joker ve Düzenli İfade Araması” dersinde ne öğreneceğim?
Belirli derinlikteki tüm çocuklara dallanarak '.' joker karakter eşleşmesini destekleyin ve tasarla-ekle-ve-sözcüklerde-ara veri yapısı problemini çözü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 3. dersidir.
“Trie’da Joker ve Düzenli İfade Araması” 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