ระยะห่างการแก้ไขทีละขั้น
แทรก ลบ และแทนที่เพื่อแปลงข้อมูล
ระยะห่างการแก้ไขทีละขั้น เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ระยะห่างการแก้ไขวัดอะไร
ระยะห่างการแก้ไขคือจำนวนการแก้ไขอักขระเดี่ยวที่น้อยที่สุดในการเปลี่ยนสตริงหนึ่งให้เป็นอีกสตริงหนึ่ง ค่านี้บอกว่าสองคำแตกต่างกันจริง ๆ มากเพียงใด
การดำเนินการสามแบบ
ในการแก้ไขแต่ละครั้ง คุณสามารถแทรก ลบ หรือแทนที่อักขระหนึ่งตัวได้ ในปัญหามาตรฐาน การดำเนินการแต่ละแบบมีต้นทุนเท่ากับหนึ่งพอดี
กำหนดสถานะ
ให้ dp[i][j] เป็นจำนวนการแก้ไขเพื่อเปลี่ยนอักขระ i ตัวแรกของ A ให้เป็นอักขระ j ตัวแรกของ B
การตรงกันที่ไม่เสียค่าใช้จ่าย
หากอักขระปัจจุบันตรงกันอยู่แล้ว ก็ไม่จำเป็นต้องแก้ไข เพียงส่งต่อค่าแนวทแยงลงมาโดยตรง
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]หากไม่ตรงกัน ให้จ่ายหนึ่ง
เมื่ออักขระต่างกัน ให้เลือกเพื่อนบ้านที่มีต้นทุนต่ำที่สุดแล้วบวกการแก้ไขอีกหนึ่งครั้ง การเลือกค่าต่ำสุดบวกหนึ่งครอบคลุมการดำเนินการทั้งสามแบบ
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])เพื่อนบ้านแต่ละด้านหมายถึงอะไร
เซลล์ด้านบนหมายถึงการลบ เซลล์ด้านซ้ายหมายถึงการแทรก และเซลล์แนวทแยงหมายถึงการแทนที่ การหาค่าต่ำสุดจะเลือกทางที่มีต้นทุนต่ำที่สุด
กรณีฐานของสตริงว่าง
การเปลี่ยนสตริงที่มีความยาว i ให้เป็นสตริงว่างต้องลบ i ครั้ง ดังนั้นให้เติมแถวและคอลัมน์แรกด้วย 0, 1, 2 ไปเรื่อย ๆ
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jกำหนดขนาดตาราง
ใช้ตารางขนาด n+1 คูณ m+1 เพื่อให้ส่วนต้นที่ว่างเปล่ามีแถวและคอลัมน์เป็นของตัวเอง การเติมช่องว่างนี้ทำให้ลูปเรียบง่าย
dp = [[0] * (m+1) for _ in range(n+1)]เติมค่าตามลำดับ
วนค่า i และ j เพิ่มขึ้นจาก 1 ทุกเซลล์ขึ้นอยู่กับเพื่อนบ้านด้านบน ด้านซ้าย และแนวทแยงที่เติมค่าแล้วเท่านั้น
for i in range(1, n+1):
for j in range(1, m+1):
...อ่านระยะห่าง
จำนวนการแก้ไขที่น้อยที่สุดจะไปอยู่ที่มุมตาราง คำตอบของคุณคือ dp[n][m] หลังจากเติมตารางเสร็จสมบูรณ์
distance = dp[n][m]ต้นทุนและรูปแบบอื่น
วิธีนี้ใช้เวลา O(n times m) งานจริงอาจกำหนดต้นทุนของการดำเนินการแต่ละแบบแตกต่างกัน แต่สมการเวียนเกิดเดิมยังคงใช้ได้
ตรวจสอบความเข้าใจ
อักขระ A[i-1] และ B[j-1] ต่างกัน สมการเวียนเกิดใดให้ค่าระยะห่างการแก้ไข
สรุปทบทวน: ระยะห่างการแก้ไข
ถ้าตรงกัน ให้ส่งต่อค่าแนวทแยง หากไม่ตรงกัน ให้ใช้หนึ่งบวกค่าต่ำสุดของเพื่อนบ้านทั้งสาม กำหนดค่าขอบตาราง แล้วอ่านค่าdp[n][m] ✏️
คำถามที่พบบ่อย
บทเรียน “ระยะห่างการแก้ไขทีละขั้น” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ระยะห่างการแก้ไขทีละขั้น” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ระยะห่างการแก้ไขทีละขั้น”
แทรก ลบ และแทนที่เพื่อแปลงข้อมูล คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “ระยะห่างการแก้ไขทีละขั้น” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การนับพาธบนกริด
- ผลรวมพาธต่ำสุดเมื่อมีสิ่งกีดขวาง
- ลำดับร่วมที่ยาวที่สุด
- ระยะห่างการแก้ไขทีละขั้น