ทรีไตรสำหรับค้นหาคำนำหน้า
จัดเก็บและค้นหาคำนำหน้าคำอย่างรวดเร็ว
ทรีไตรสำหรับค้นหาคำนำหน้า เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
จัดเก็บคำอย่างชาญฉลาด
ทรีคำนำหน้าคือต้นไม้ที่จัดเก็บคำโดยใช้คำนำหน้าร่วมกัน ทำให้ตอบคำถามเกี่ยวกับคำนำหน้าได้อย่างรวดเร็วมาก 🌳
ทำไมไม่ใช้เซตอย่างเดียว
เซตใช้ค้นหาคำทั้งคำได้ แต่ทรีคำนำหน้ายังตอบคำถามเกี่ยวกับ คำนำหน้าได้ด้วย เช่น มีคำใดเริ่มต้นด้วย pre หรือไม่
โหนดและเส้นเชื่อม
แต่ละ โหนดคือตำแหน่งหนึ่งในคำ และเส้นเชื่อมแต่ละเส้นมีอักขระกำกับอยู่บนเส้นทางจากราก
โหนดในรูปพจนานุกรม
ใน Python โครงสร้าง โหนดที่สร้างได้ง่ายที่สุดคือพจนานุกรมที่จับคู่อักขระกับโหนดลูกของมัน ทั้งกระชับและยืดหยุ่น
root = {}แทรกคำ
ในการ แทรก ให้เดินไปทีละอักขระและสร้างโหนดลูกขึ้นเมื่อยังไม่มีโหนดนั้น
node = root
for c in word:
node = node.setdefault(c, {})ทำเครื่องหมายจุดสิ้นสุดคำ
หลังจากแทรกแล้ว ให้ตั้งค่าสถานะ จุดสิ้นสุด เพื่อแยกคำทั้งคำออกจากคำนำหน้าเพียงบางส่วนได้
node['#'] = Trueค้นหาคำทั้งคำ
ในการ ค้นหา ให้เดินตามอักขระไปทีละตัว หากขั้นตอนไหนไม่มีโหนด คำนั้นก็ไม่มีอยู่ จากนั้นตรวจสอบสถานะจุดสิ้นสุด
for c in word:
if c not in node:
return False
node = node[c]ตรวจสอบคำนำหน้า
การค้นหา คำนำหน้าใช้การเดินแบบเดียวกัน แต่ไม่ต้องตรวจสอบสถานะจุดสิ้นสุด หากเดินถึงโหนดสุดท้ายได้ ก็ถือว่าพบ
ความซับซ้อนด้านเวลา
การแทรกและการค้นหาใช้เวลา O(L) โดย L คือความยาวของคำ ไม่ว่าคุณจะจัดเก็บคำไว้กี่คำ สิ่งที่สำคัญคือความยาว
นับคำตามคำนำหน้า
จัดเก็บ จำนวนไว้ที่แต่ละโหนด เพื่อให้ตอบได้ทันทีว่ามีคำที่จัดเก็บไว้กี่คำใช้คำนำหน้าที่กำหนดร่วมกัน
จุดที่ทรีคำนำหน้าช่วยได้
ทรีคำนำหน้าช่วยในการ เติมข้อความอัตโนมัติ การตรวจสอบพจนานุกรม และปัญหาการหาค่าสูงสุดด้วย XOR บนบิต ซึ่งเป็นโครงสร้างพื้นฐานของโจทย์สตริงในการแข่งขัน
ตรวจสอบอย่างรวดเร็ว
ยืนยันว่าการค้นหาในทรีคำนำหน้ามีต้นทุนเท่าใด
ทบทวน: ทรีคำนำหน้าพร้อมใช้งาน
ขณะนี้คุณสามารถสร้าง ทรีคำนำหน้า แทรกและค้นหาได้ใน O(L) รวมทั้งตอบคำถามเกี่ยวกับคำนำหน้าและจำนวนได้อย่างรวดเร็ว 🌟
เรียนรู้ Python ด้วย AI tutor — ฟรี
เขียนและเรียกใช้โค้ดจริงในเบราว์เซอร์ของคุณ รับความช่วยเหลือทันทีจาก AI tutor 24/7 และเรียนรู้ต่อจากที่คุณหยุดบนเว็บหรือในแอป
- คอร์ส
- 30
- บทเรียน
- 120
คำถามที่พบบ่อย
บทเรียน “ทรีไตรสำหรับค้นหาคำนำหน้า” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ทรีไตรสำหรับค้นหาคำนำหน้า” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ทรีไตรสำหรับค้นหาคำนำหน้า”
จัดเก็บและค้นหาคำนำหน้าคำอย่างรวดเร็ว คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “ทรีไตรสำหรับค้นหาคำนำหน้า” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ฟังก์ชันคำนำหน้า KMP
- แฮชสตริงพหุนาม
- ฟังก์ชัน Z สำหรับค้นหารูปแบบ
- ทรีไตรสำหรับค้นหาคำนำหน้า