การค้นหาคำ II: Trie + การย้อนกลับบนกริด
แทรกคำเป้าหมายทั้งหมดลงใน trie และเรียกใช้ DFS แบบย้อนกลับบนกระดานสองมิติเพื่อค้นหาคำที่ถูกต้องทั้งหมดพร้อมกันในเวลา O(m × n × 4^L)
การค้นหาคำ II: Trie + การย้อนกลับบนกริด เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาการค้นหาคำ II
การค้นหาคำ II (LeetCode 212): เมื่อกำหนดกระดานอักขระขนาด m × n และรายการคำ ให้ค้นหาคำทั้งหมดที่สามารถสร้างได้จากเซลล์ที่อยู่ติดกันตามลำดับ (แนวนอนหรือแนวตั้ง) โดยแต่ละเซลล์ใช้ได้เพียงครั้งเดียว ปัญหานี้ยากกว่าการค้นหาคำ I (คำเดียว) เพราะเราต้องค้นหาคำที่ตรงกัน ทั้งหมด พร้อมกัน — หากเรียกใช้การค้นหาคำ I แยกสำหรับแต่ละคำแบบตรงไปตรงมา จะใช้เวลา O(W × m × n × 4^L) ซึ่งช้าเกินไป
เหตุใดจึงใช้ไทรร่วมกับการย้อนรอย
การแทรกคำเป้าหมายทั้งหมดลงใน ไทร แล้วทำการย้อนรอยด้วย DFS บนกระดาน ช่วยให้เราค้นหาคำทั้งหมดพร้อมกันได้ ในแต่ละเซลล์ของกระดาน แทนที่จะตรวจสอบว่า 'เส้นทางนี้สะกดคำเป้าหมายของฉันหรือไม่' เราจะตรวจสอบว่า 'เส้นทางนี้ตรงกับคำนำหน้าในไทรหรือไม่' ทันทีที่คำนำหน้าในไทรไม่ตรงกัน เราจะตัดกิ่ง DFS ทั้งกิ่งออก จึงหลีกเลี่ยงการทำงานซ้ำระหว่างคำทั้งหมดที่ใช้คำนำหน้าร่วมกัน
การสร้างไทรจากรายการคำ
แทรกคำทั้งหมดลงในไทร เก็บคำที่สมบูรณ์ไว้ที่โหนดปลาย (ใน node.word) แทนที่จะเก็บเพียงค่าบูลีน เพื่อเมื่อพบการจับคู่ที่สมบูรณ์ระหว่างการย้อนรอย เราจะเพิ่มคำนั้นลงในผลลัพธ์ได้ทันทีโดยไม่ต้องสร้างคำขึ้นใหม่ทีละอักขระ
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')การย้อนรอยด้วย DFS บนตาราง
เริ่ม DFS จากทุกเซลล์บนกระดาน ในแต่ละขั้นตอน: (1) ตรวจสอบว่าอักขระของเซลล์ปัจจุบันมีอยู่เป็นโหนดลูกในโหนดไทรปัจจุบันหรือไม่ (2) หากมี ให้ทำเครื่องหมายว่าเซลล์ถูกเยี่ยมชมแล้ว (กำหนดค่าเป็นค่าพิเศษ เช่น '#') แล้วเรียกซ้ำไปยังเซลล์ข้างเคียงทั้ง 4 เซลล์ (3) หลังจากการเรียกซ้ำเสร็จสิ้น ให้คืนค่าเดิมของเซลล์ (ยกเลิกเครื่องหมาย) เมื่อโหนดไทรมี word ที่ไม่ว่าง ให้เพิ่มคำนั้นลงในผลลัพธ์และกำหนดค่าเป็นว่าง เพื่อหลีกเลี่ยง duplicates
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']การวิเคราะห์ความซับซ้อน
เวลา: O(m × n × 4^L) โดย L คือความยาวคำสูงสุด สำหรับเซลล์เริ่มต้นแต่ละเซลล์จากทั้งหมด m×n เซลล์ DFS จะสำรวจเส้นทางได้มากถึง 4^L เส้นทาง ไทรจะตัดเส้นทางที่ไม่ตรงกับคำนำหน้าของคำใด ๆ ออก ดังนั้นในทางปฏิบัติจึงทำงานได้เร็วขึ้นมาก การสร้างไทรใช้เวลา O(W × L) โดย W คือจำนวนคำ พื้นที่: O(W × L) สำหรับไทร และ O(L) สำหรับความลึกของสแตกการเรียกซ้ำ
การตัดกิ่ง: ลบโหนดปลายหลังจากพบคำ
หลังจากพบคำแล้ว ให้ ลบโหนดปลายออกจากไทร (ไม่ใช่เพียงกำหนดคำให้เป็นค่าว่าง) หากโหนดนั้นไม่มีโหนดลูก การทำเช่นนี้ช่วยป้องกันการกลับไปเยี่ยมกิ่งที่ไม่มีทางไปต่อในการเรียก DFS ครั้งถัดไป เมื่อโหนดลูกของโหนดหนึ่งไม่มีเหลือหลังจากพบคำแล้ว ให้ลบโหนดนั้นออกจากพจนานุกรมโหนดลูกของโหนดแม่ การปรับปรุงนี้มีนัยสำคัญเมื่อหลายคำใช้คำนำหน้ายาวร่วมกัน
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')เหตุใดการเก็บ word ไว้ในโหนดจึงดีกว่า
การเก็บคำที่สมบูรณ์ไว้ที่โหนดปลายของไทร (แทนการสร้างคำใหม่จากเส้นทาง DFS) มีข้อดีสองประการ: (1) ดึงคำได้ในเวลา O(1) เมื่อพบการจับคู่ แทนการสร้างเส้นทางใหม่ซึ่งใช้เวลา O(L) (2) การกำหนด node.word = None หลังพบคำเป็นวิธีกำจัดรายการซ้ำที่สะอาดและใช้เวลา O(1) โดยไม่ต้องมีเซตผลลัพธ์แยกต่างหาก โดยเฉพาะสำหรับการค้นหาคำ II การป้องกันคำซ้ำมีความสำคัญ เพราะในทางทฤษฎีคำเดียวกันอาจถูกพบผ่านเส้นทางที่แตกต่างกัน
การทำเครื่องหมายเซลล์ที่เยี่ยมชมแล้วโดยตรงในข้อมูล
แทนที่จะใช้เซต visited แยกต่างหาก (ซึ่งจะต้องใช้พื้นที่ O(m × n) ต่อเส้นทาง DFS) เราจะทำเครื่องหมายเซลล์โดยตรงด้วยการแทนที่อักขระด้วยค่าพิเศษ เช่น '#' หลัง DFS คืนค่าแล้ว ให้คืนอักขระเดิมกลับมา เทคนิคนี้ (1) ใช้พื้นที่เพิ่มเติม O(1) ต่อเซลล์ (2) ป้องกันการกลับไปเยี่ยมเซลล์เดิมภายในเส้นทางเดียวโดยอัตโนมัติ (3) ไม่รบกวนการเดินผ่านไทรเลย เนื่องจาก '#' จะไม่มีอยู่ในไทร
กรณีขอบที่ต้องจัดการ
กรณีขอบที่สำคัญ: (1) คำซ้ำในรายการคำ — จัดเก็บไว้ในเซต หรือใช้วิธีกำหนด node.word = None เพื่อป้องกันคำซ้ำในผลลัพธ์ (2) คำที่ยาวมากจนเกินขนาดกระดาน — ไม่สามารถสร้างขึ้นได้ แต่ DFS จะจัดการกรณีนี้ตามธรรมชาติเมื่อไม่มีเซลล์ข้างเคียงให้เดินต่อ (3) กระดานเซลล์เดียว — พบได้เฉพาะคำที่มีอักขระเดียว (4) คำเดียวกันที่สามารถพบได้ผ่านเส้นทางต่างกัน — วิธีกำหนด node.word = None จะป้องกันการนับซ้ำ
การเปรียบเทียบกับวิธีแบบตรงไปตรงมา
วิธีแบบตรงไปตรงมา: สำหรับคำ W คำ ให้ทำการค้นหาคำ I แยกกัน ใช้เวลา O(W × m × n × 4^L) เมื่อใช้ไทร คำทั้งหมดจะถูกค้นหาพร้อมกัน ใช้เวลา O(m × n × 4^L) โดยไม่ขึ้นกับ W สำหรับ W=1000 คำที่มีความยาว 10 บนกระดานขนาด 10×10 วิธีแบบตรงไปตรงมาจะช้ากว่าไทร 1000 เท่า ไทรทำหน้าที่เป็นตัวกรองคำนำหน้าร่วม ซึ่งช่วยเฉลี่ยต้นทุนของคำทั้งหมด — เป็นตัวอย่างคลาสสิกของการใช้โครงสร้างข้อมูลเพื่อให้ได้การปรับปรุงเชิงเส้นกำกับ
สรุปวิธีแก้ปัญหาฉบับเต็ม
วิธีแก้ปัญหาการค้นหาคำ II ฉบับสมบูรณ์: สร้างไทรด้วยคำต่าง ๆ และเก็บสตริงคำไว้ที่โหนดปลาย สำหรับแต่ละเซลล์บนกระดาน ให้ทำ DFS โดยตรวจสอบว่าอักขระปัจจุบันมีอยู่ในโหนดไทรปัจจุบันหรือไม่ ทำเครื่องหมายเซลล์เป็น '#' เรียกซ้ำไปยังเซลล์ข้างเคียงทั้ง 4 เซลล์ แล้วคืนค่าเดิมของเซลล์ เมื่อ node.word ไม่ว่าง ให้เพิ่มลงในผลลัพธ์และกำหนดให้ว่าง อาจตัดกิ่งไทรที่ว่างเปล่าหลังใช้งานได้ตามต้องการ คืนค่ารายการผลลัพธ์ เวลา: O(m×n×4^L), พื้นที่: ไทร O(W×L) + การเรียกซ้ำ O(L)
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 resultตรวจสอบความเข้าใจอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
สรุปบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า การค้นหาคำ II ใช้ไทรเพื่อให้ค้นหาหลายคำพร้อมกันได้ โดยตัดกิ่งจากคำนำหน้าที่ใช้ร่วมกัน การเก็บสตริงคำไว้ในโหนดปลายของไทรช่วยให้ดึงคำได้ในเวลา O(1) และกำจัดคำซ้ำได้ง่ายด้วยการตั้งค่าเป็นค่าว่างหลังจากพบคำ และ การทำเครื่องหมายเซลล์ที่เยี่ยมชมแล้วโดยตรงด้วย '#' ช่วยหลีกเลี่ยงการใช้พื้นที่เพิ่มเติม O(m×n) ต่อเส้นทาง DFS บทนี้เป็นบทสรุปของหลักสูตรไทรและอัลกอริทึมสตริง — คุณได้เชี่ยวชาญหนึ่งในโครงสร้างข้อมูลเฉพาะสำหรับสตริงที่ทรงพลังที่สุดซึ่งใช้ในการสัมภาษณ์แล้ว
คำถามที่พบบ่อย
บทเรียน “การค้นหาคำ II: Trie + การย้อนกลับบนกริด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การค้นหาคำ II: Trie + การย้อนกลับบนกริด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การค้นหาคำ II: Trie + การย้อนกลับบนกริด”
แทรกคำเป้าหมายทั้งหมดลงใน trie และเรียกใช้ DFS แบบย้อนกลับบนกระดานสองมิติเพื่อค้นหาคำที่ถูกต้องทั้งหมดพร้อมกันในเวลา O(m × n × 4^L) คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “การค้นหาคำ II: Trie + การย้อนกลับบนกริด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- คลาส TrieNode: แทรกและค้นหา
- การค้นหาคำนำหน้าและ Starts-With
- การค้นหาแบบไวลด์การ์ดและนิพจน์ประจำใน Trie
- การค้นหาคำ II: Trie + การย้อนกลับบนกริด