การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie
รองรับการจับคู่ไวลด์การ์ด '.' ด้วยการแตกแขนงไปยังลูกทุกตัวในระดับนั้น และแก้ปัญหาโครงสร้างข้อมูลสำหรับเพิ่มและค้นหาคำ
การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาการค้นหาด้วยอักขระตัวแทน
การค้นหาในไทรแบบมาตรฐานรองรับอักขระที่ตรงกันทุกประการ ส่วน การค้นหาด้วยอักขระตัวแทน จะเพิ่มอักขระพิเศษ '.' ซึ่งตรงกับอักขระใดก็ได้หนึ่งตัว เมื่อพบ '.' ระหว่างการค้นหา แทนที่จะเดินตามโหนดลูกเพียงตัวเดียว เราต้องลองกับ โหนดลูกทั้งหมด ซึ่งเป็นการแตกแขนง แนวคิดหลักนี้อยู่เบื้องหลังโจทย์ LeetCode 211 เรื่อง 'การออกแบบโครงสร้างข้อมูลสำหรับเพิ่มและค้นหาคำ' โดย '.' แต่ละตัวจะเพิ่มจำนวนเส้นทางการค้นหาเป็นเท่าตัวตามจำนวนโหนดลูกในระดับนั้น
การค้นหาด้วยอักขระตัวแทนแบบเรียกซ้ำ
นำการค้นหาด้วยอักขระตัวแทนไปใช้ด้วยตัวช่วย DFS แบบเรียกซ้ำ สำหรับอักขระแต่ละตัวในรูปแบบ หากเป็นอักขระตรงตัว ให้เดินตามโหนดลูกที่ระบุ (หรือคืนค่าเป็นเท็จหากไม่พบ) หากเป็น '.' ให้เรียกซ้ำกับโหนดลูกทั้งหมดและคืนค่าเป็นจริงหากมีเส้นทางใดสำเร็จ เมื่อถึงจุดสิ้นสุดของรูปแบบ ให้คืนค่า node.is_end
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')) # Falseเหตุใดจึงใช้การตรวจสอบค่าจริงสำหรับการแตกแขนง
เมื่อพบ '.' เราจะเรียก any(dfs(child, i+1) for child in node.children.values()) ตัวสร้างสำหรับตรวจสอบว่ามีค่าใดเป็นจริงจะทำงานแบบลัดวงจร คือหยุดทันทีที่โหนดลูกตัวใดตัวหนึ่งคืนค่าเป็นจริง จึงหลีกเลี่ยงการสำรวจที่ไม่จำเป็นได้ ในกรณีเลวร้ายที่สุด (รูปแบบที่เป็น '.' ทั้งหมด) เราจะสำรวจทุกเส้นทาง โดยมีความซับซ้อนเป็น O(26^k) เมื่อ k คือจำนวนจุด ทำให้รูปแบบอย่าง '....' ใช้เวลามากสำหรับไทรขนาดใหญ่
การค้นหาด้วยอักขระตัวแทนแบบวนซ้ำโดยใช้คิว
วิธีแบบวนซ้ำใช้คิวของคู่ (node, index) เริ่มต้นด้วย (root, 0) สำหรับแต่ละคู่ หาก index == len(word) และ node.is_end ให้คืนค่าเป็นจริง มิฉะนั้นให้ประมวลผลอักขระปัจจุบัน: สำหรับ '.' ให้เพิ่มโหนดลูกทั้งหมดลงในคิว ส่วนอักขระตรงตัวให้เพิ่มเฉพาะโหนดลูกที่ตรงกัน วิธีนี้โดยพื้นฐานแล้วคือ BFS บนเส้นทางของไทร
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')การวิเคราะห์ความซับซ้อนของการค้นหาด้วยอักขระตัวแทน
สำหรับรูปแบบที่ไม่มีอักขระตัวแทน การค้นหาใช้เวลา O(m) สำหรับรูปแบบที่มีอักขระตัวแทน k ตัว กรณีเลวร้ายที่สุดคือ O(26^k × m) ซึ่งเพิ่มขึ้นแบบเอ็กซ์โพเนนเชียลตามจำนวนอักขระตัวแทน ในทางปฏิบัติ อักขระตัวแทนมักมีอยู่ไม่มากและไทรมักมีความลึกไม่มาก ประสิทธิภาพจึงอยู่ในระดับที่ยอมรับได้ สำหรับรูปแบบที่เป็นอักขระตัวแทนทั้งหมด (เช่น การจับคู่คำทั้งหมดที่มีความยาว k) วิธีนี้จะเสื่อมลงเป็นการเดินผ่านไทรทั้งหมด
การค้นหาด้วยนิพจน์ประจำที่มากกว่าอักขระตัวแทนเดี่ยว
การขยายไปสู่นิพจน์ประจำแบบเต็มรูปแบบ (เช่น '*' ที่ตรงกับอักขระตั้งแต่ศูนย์ตัวขึ้นไป) จำเป็นต้องจัดการด้วยวิธีอื่น '*' สามารถตรงกับส่วนต่อท้ายใดก็ได้ ดังนั้นเมื่อพบอักขระนี้ เราต้องลองทุกเส้นทางของไทรจากโหนดปัจจุบัน การจับคู่ด้วยนิพจน์ประจำจริงในไทรมีความซับซ้อน โดยทั่วไปจึงสงวนไว้สำหรับการสร้าง NFA/DFA สำหรับการสัมภาษณ์ อักขระตัวแทนหนึ่งตัว ('.') คือรูปแบบมาตรฐาน
การจับคู่รูปแบบโกลบ
การจับคู่รูปแบบโกลบ ด้วย '?' (อักขระใดก็ได้หนึ่งตัว) และ '*' (ลำดับอักขระใดก็ได้ รวมถึงลำดับว่าง) สามารถทำได้ด้วย DP หากนำไปใช้ในไทร '?' จะสอดคล้องกับการแตกแขนงหนึ่งระดับ (เช่นเดียวกับ '.') และ '*' จะสอดคล้องกับ DFS หลายระดับ วิธี DP แบบผสมคือ dp[i][j] = จริง หาก pattern[0..i] ตรงกับ string[0..j] โดยทั่วไปผู้สัมภาษณ์จะระบุว่าต้องนำรูปแบบใดไปใช้
การประยุกต์ใช้จริง: การกำหนดเส้นทางที่อยู่ IP
ไทรที่รองรับอักขระตัวแทนถูกใช้ใน ตารางกำหนดเส้นทาง IP โดย '*' ทำหน้าที่เป็นอักขระตัวแทนของคำนำหน้า เราเตอร์จะจัดเก็บคำนำหน้าเส้นทาง เช่น '192.168.*' และจับคู่กับที่อยู่ขาเข้า การจับคู่คำนำหน้าที่ยาวที่สุด (เส้นทางที่เฉพาะเจาะจงที่สุดจะเป็นผู้ชนะ) ทำได้โดยเดินผ่านไทรให้ลึกที่สุดเท่าที่ทำได้และใช้ผลการจับคู่ล่าสุดที่พบ นี่คือการประยุกต์ใช้การทำงานกับคำนำหน้าและอักขระตัวแทนของไทรในโลกจริง
การปรับปรุงประสิทธิภาพ: การตัดกิ่งที่ไม่มีทางไปต่อ
เมื่อโหนดไทรไม่มีโหนดลูก (เป็นโหนดปลาย) และ is_end = False การค้นหาใด ๆ ที่มาถึงโหนดนี้จะคืนค่าเป็นเท็จ ระหว่างการค้นหาด้วยอักขระตัวแทน การข้ามโหนดปลายตันเหล่านี้ก่อนเรียกซ้ำจะช่วยตัดการเรียกที่ไม่จำเป็นได้ การเก็บ word_count ในแต่ละโหนด (จำนวนคำทั้งหมดในต้นไม้ย่อย) ช่วยให้เราข้ามต้นไม้ย่อยทั้งต้นได้ หากไม่มีคำใดตรงกับข้อจำกัดด้านความยาวของรูปแบบที่เหลืออยู่
คลาส WordDictionary ฉบับเต็มพร้อมใช้ในการสัมภาษณ์
WordDictionary ที่สะอาดและพร้อมใช้ในการสัมภาษณ์ ซึ่งรวมการแทรกและการค้นหาด้วยอักขระตัวแทนจุดไว้ในคลาสเดียว นี่คือการนำไปใช้ที่คาดหวังอย่างตรงตัวสำหรับ LeetCode 211 การค้นหาแบบเรียกซ้ำที่ใช้การหยุดทันทีเมื่อพบผลลัพธ์ที่สำเร็จนั้นกระชับ และแสดงตรรกะการแตกแขนงให้ผู้สัมภาษณ์เห็นได้อย่างชัดเจน
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.')) # Falseการใช้ setdefault สำหรับไทรแบบกระชับ
dict.setdefault(key, default) จะคืนค่าของ key หากมีอยู่แล้ว มิฉะนั้นจะแทรก default แล้วคืนค่าดังกล่าว การใช้ node.setdefault(c, {}) ในการแทรกช่วยตัดการตรวจสอบแบบเงื่อนไขถ้า-มิฉะนั้นออกไป โดยจะสร้างพจนานุกรมของโหนดลูกหากยังไม่มี และคืนค่าให้ไม่ว่าจะมีอยู่ก่อนหรือไม่ ทำให้การแทรกเป็นการเดินผ่านในบรรทัดเดียว: for c in word: node = node.setdefault(c, {}) สะอาดและเป็นรูปแบบที่เหมาะกับภาษาไพธอน
ตรวจสอบความเข้าใจอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
สรุปบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า อักขระตัวแทน '.' จำเป็นต้องแตกแขนงไปยังโหนดลูกทั้งหมดที่ตำแหน่งตรงกันโดยใช้ DFS แบบเรียกซ้ำ การใช้การประเมินแบบลัดวงจรร่วมกับตัวสร้างค่าช่วยให้หยุดการทำงานได้เร็ว และ setdefault ช่วยให้การแทรกลงในไทรทำได้กระชับในบรรทัดเดียว บทถัดไป เราจะผสานไทรกับการย้อนรอยเพื่อแก้ปัญหาการค้นหาคำ II — ค้นหาหลายคำพร้อมกันบนกระดานสองมิติ
คำถามที่พบบ่อย
บทเรียน “การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie”
รองรับการจับคู่ไวลด์การ์ด '.' ด้วยการแตกแขนงไปยังลูกทุกตัวในระดับนั้น และแก้ปัญหาโครงสร้างข้อมูลสำหรับเพิ่มและค้นหาคำ คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- คลาส TrieNode: แทรกและค้นหา
- การค้นหาคำนำหน้าและ Starts-With
- การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie
- การค้นหาคำ II: Trie + การย้อนกลับบนกริด