題目與適用情境
給定字串 source 和 target，回傳把 source 轉換成 target 所需的最少編輯次數。一次編輯可以 插入一個字元、刪除一個字元或替換一個字元，每種操作的成本都是一。任一字串都可能為空，且兩者只含 小寫英文字母。
source = "horse"
target = "ros"
horse -> rorse 把 h 替換為 r
rorse -> rose 刪除 r
rose -> ros 刪除 e
答案 = 3設 m = source.length、n = target.length，兩個長度都不超過 2,000。題目只要求最小成本，不要求 回傳編輯步驟。Wagner–Fischer 論文把字串校正定義為插入、刪除和替換組成的最小成本序列，並提出 時間與兩個字串長度乘積成正比的演算法。2026 年的公開面試指南仍把編輯距離當成雙字串動態規劃的 典型練習。這些資料能說明本題目前的準備價值，但不能證明特定公司的出題頻率或歸屬。
編輯距離可用於拼字檢查、模糊比對、紀錄關聯和序列比較，不過正式環境的定義可能加入操作權重、字元 交換、正規化或領域專用 token。面試版本刻意限制為單位成本的字元編輯，讓狀態和證明都有明確邊界。
面試官考察重點
第一個訊號是能給出邊界精確的狀態定義。令 dp[i][j] 表示把 source 的前 i 個字元變成 target 的前 j 個字元所需的最少編輯次數。只說「i 和 j 之前的答案」過於含糊，無法證明 轉移，也無法初始化空前綴。
第二個訊號是能推導末尾字元不同時的三種轉移。一個最佳方案的最後一步只能是刪除、插入或替換； 移除這最後一步後，剩下的正是一個更小的前綴問題。候選人應把每種操作對應到正確的相鄰儲存格， 而不是死記三個座標。
第三個訊號是末尾字元相同時不憑空增加操作。若 source[i - 1] 等於 target[j - 1]，最佳方案可 保留這個字元，值來自 dp[i - 1][j - 1]。證明還要說明這樣做不會漏掉成本更低的方案。
第四個訊號是看清相依形狀。一列只相依於上一列和本列左側儲存格；只回傳距離時，不必保存完整的 O(mn) 矩陣。讓較短字串作為欄，就能把額外空間降為 O(min(m, n))。
最後一個訊號是始終遵守題目契約。此處插入和刪除都是單位成本，距離具有對稱性，因此可以交換列與欄 的字串；若插入和刪除權重不同，就不能預設交換。Unicode 文字還必須明確定義比較單位究竟是 UTF-16 碼元、Unicode 碼點，還是使用者看到的字素叢集。
回答前需要釐清的問題
- 允許哪些操作？ 本題允許插入、刪除和替換，相鄰字元交換不算一次操作。
- 每次編輯成本是多少？ 三種操作成本都為一。加權成本會改變遞迴式，也可能讓距離失去對稱性。
- 比較單位是什麼？ 題目只有小寫英文字母，所以目前 JavaScript 實作可以安全使用索引。一般
Unicode 文字需要另行約定。
- 只回傳距離還是回傳編輯步驟？ 只回傳距離。重建操作通常要保留完整表格或明確的前驅資訊。
- 輸入可以為空嗎？ 可以。空字串變成長度為
j的前綴恰好需要j次插入，反向則需要i
次刪除。
- 輸入規模多大？ 長度不超過 2,000，
O(mn)時間可接受，但指數遞迴和不必要的完整矩陣記憶體
不合適。
- 能否交換兩個輸入以節省記憶體？ 在目前單位成本契約下可以，因為距離對稱；使用前要先說明
這個前提。
30 秒回答架構
「我定義 dp[i][j] 為來源字串前 i 個字元到目標字串前 j 個字元的最少編輯次數。空前綴 成本初始化第一列和第一欄。末尾字元相等時直接取左上角；不相等時，最後一步只能是刪除、插入或 替換，所以取上方、左側和左上角的最小值再加一。每個儲存格只相依於上一列及本列左側，因此把短字串 放在欄上，只保存兩列。時間是 O(mn)，空間是 O(min(m, n))。我會涵蓋空字串、相同字串、 長度不對稱情況，並在小型輸入上與完整矩陣實作對照。」
分步深入解答
從前綴開始定義。令 dp[i][j] 表示把 source[0..i - 1] 轉換為 target[0..j - 1] 所需的 最少允許操作數。
空前綴邊界直接來自題目契約：
dp[0][j] = j // 插入目標的全部 j 個字元
dp[i][0] = i // 刪除來源的全部 i 個字元對兩個非空前綴，觀察它們的末尾字元。若末尾相同，保留這個共同字元，問題縮小為兩個更短的前綴：
如果 source[i - 1] == target[j - 1]：
dp[i][j] = dp[i - 1][j - 1]若末尾不同，對任意最佳操作序列的最後一次編輯分類：
刪除 source[i - 1]： dp[i - 1][j] + 1
插入 target[j - 1]： dp[i][j - 1] + 1
替換末尾字元： dp[i - 1][j - 1] + 1
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])三種情況完備，因為最後一步必然是題目允許的三種操作之一；它們也都可構造：在所選小前綴的最佳 方案後附加對應編輯，就能得到 (i, j) 的合法方案。反過來，從任意最佳方案中移除最後一步，剩餘 部分正在解決對應的小前綴，成本不可能低於那個儲存格。因此字元不同時的遞迴式成立。
末尾字元相同時，至少存在一個最佳方案讓它們直接配對。若某個最佳序列仍編輯了來源或目標的末尾， 可以移除這些末尾影響，改為對齊兩個相同字元，成本不會增加；剩餘工作正是左上角前綴問題。以空前綴 為基礎，對 i + j 做歸納，就能證明每個儲存格以及最終的 dp[m][n] 都正確。
填一列時只需要三個舊值：刪除對應 previous[j]，插入對應 current[j - 1]，替換或配對對應 previous[j - 1]。程式碼讓短字串作為欄。這是在目前對稱單位成本定義下的記憶體最佳化，不會 改變答案。
export function editDistance(source: string, target: string): number {
const rows = source.length >= target.length ? source : target
const columns = source.length >= target.length ? target : source
let previous = Array.from(
{ length: columns.length + 1 },
(_, index) => index,
)
for (let row = 1; row <= rows.length; row += 1) {
const current = new Array<number>(columns.length + 1)
current[0] = row
for (let column = 1; column <= columns.length; column += 1) {
if (rows[row - 1] === columns[column - 1]) {
current[column] = previous[column - 1]
continue
}
const deleteCost = previous[column] + 1
const insertCost = current[column - 1] + 1
const replaceCost = previous[column - 1] + 1
current[column] = Math.min(deleteCost, insertCost, replaceCost)
}
previous = current
}
return previous[columns.length]
}對 source = "horse"、target = "ros"，較短的欄維度長度為三，最後一列的末項是三，與一次替換 加兩次刪除的操作序列一致。演算法只回傳成本，不宣稱這條具體編輯序列是唯一答案。
複雜度、邊界與工程取捨
演算法在概念上填入 (m + 1)(n + 1) 個狀態，因此時間複雜度為 O(mn)。每列有 min(m, n) + 1 個儲存格，且同時只保留兩列，額外空間為 O(min(m, n))。每輪建立一列不改變 漸進界；若要減少配置壓力，可以重複使用兩個陣列，演算法本身不必改變。
在單位插入、刪除和替換下，答案最大為 max(m, n)：先替換前 min(m, n) 個字元，再插入或刪除 長度差；答案最小為 |m - n|，因為一次編輯最多只讓長度改變一。這兩個界可作為測試斷言。
對一般 JavaScript 字串，索引操作的是 UTF-16 碼元。字串迭代會依 Unicode 碼點產出值，因此不會 拆開代理對，但仍可能拆開一個字素叢集，例如 emoji 與膚色修飾符或零寬連接符序列。正式環境的相似度 功能必須先決定編輯作用於碼元、碼點、正規化後的字素叢集、單字還是領域 token，再選擇切分方式。 靜默正規化也可能改變產品語意，因此它應寫進契約，而不是藏在這個 DP 迴圈裡。
若呼叫端只問距離是否不超過 k，可以先在 |m - n| > k 時直接回傳 false，再只計算一條對角帶； 當活動帶中沒有狀態還能回到預算內時提前停止。這是另一種輸出契約，完整距離實作不應為未提出的需求 擅自增加這層複雜度。
高品質示範回答
「我會把問題建模在兩個字串的前綴上。令 dp[i][j] 表示把來源字串前 i 個字元變成目標字串 前 j 個字元的最小成本，空前綴邊界就是對應長度。兩個末尾字元相同時沿用左上角；不同時，依最佳 序列的最後一次編輯分類：刪除來自上方，插入來自左側，替換來自左上角，再替三者最小值加一。這三類 涵蓋所有允許操作；反向移除最後一步，也能證明遞迴式沒有低估答案。
「每個狀態只需要上一列與本列左側，所以我保存兩列。單位插入和刪除讓距離對稱，可以把短字串放在欄 上，把記憶體降到 O(min(m, n))，時間仍為 O(mn)；非對稱權重下不能這樣交換。我會測試兩個 方向的空字串、相同字串、horse 到 ros，並用短字串把結果與完整矩陣實作對照。若面試官要求編輯 步驟，我會保留前驅資訊，不會承諾從已經覆寫的滾動陣列中重建。」
常見錯誤
- 貪心配對字元 → 重複字元和後續位移會讓局部方便的編輯錯過全域最小值 → **定義最佳前綴狀態，
比較所有合法的最後一步操作。**
- 把第一列和第一欄都初始化為零 → 空字串轉換變成免費 → 邊界成本設為對應前綴長度。
- 混淆插入和刪除的鄰居 → 程式碼可能通過對稱範例，卻在不對稱前綴上出錯 → **說明移除最後一步後
剩下哪個字串。**
- 末尾字元相同時仍加一 → 沒有變化的相同字元被誤算成替換 → 相同時直接複製左上角。
- 用滾動陣列卻承諾回傳編輯腳本 → 被覆寫的前驅無法重建路徑 → **需要操作序列時保留矩陣或
前驅。**
- 在非對稱權重下交換字串 → 一個方向的插入會變成另一個方向的刪除 → **除非成本模型對稱，
否則保持原方向。**
- 把 JavaScript 索引稱為任意 Unicode 的「字元」 → 代理對或字素叢集會被意外計數 → **明確
定義並切分比較單位。**
一組聚焦測試包括 ("", "") = 0、("", "abc") = 3、("abc", "") = 3、 ("same", "same") = 0、("aaaa", "aa") = 2、("horse", "ros") = 3 和 ("intention", "execution") = 5。可在小字母表的所有短字串上，把滾動陣列實作與完整矩陣參考 實作對照；還要檢查同一性、目前成本模型下的對稱性、|m - n| ≤ d ≤ max(m, n)，以及產生字串 三元組上的三角不等式。最後用長度為 2,000 的完全相同和完全不同輸入執行極限路徑，確認實際表現 符合平方時間、線性空間的預期。
面試追問
追問 1：如何回傳實際的編輯操作？
保留完整矩陣，再從 (m, n) 反向走。字元相同時不輸出操作並走左上角；否則選擇一個滿足「鄰居值加 對應操作成本等於目前值」的儲存格。多個最短腳本可能同時存在，因此要定義穩定的平手規則。直接方法 使用 O(mn) 空間。也能用分治方法做到線性空間重建，但那是另一套演算法，只有記憶體要求明確提出時 才值得加入。
追問 2：不同操作有不同權重時如何修改？
每條轉移加上對應權重，而不是統一加一。只要成本非負且契約明確，同樣的最佳子結構證明仍成立。若 插入和刪除權重不同，距離可能有方向性，不能再自動交換字串來縮短列。負編輯成本會破壞通常的距離 含義，需要重新檢視模型。
追問 3：如何支援相鄰字元交換？
先釐清交換是否僅限相鄰字元，以及是否允許互相重疊的交換。受限的 optimal string alignment 遞迴 可以額外檢查前兩個字元和左上兩列兩欄的狀態；完整 Damerau–Levenshtein 距離則需要不同的狀態資訊。 只隨手加一個對角判斷，很可能實作成錯誤變體。
追問 4：它與最長共同子序列有什麼關係？
若禁止替換，或替換成本等於一次刪除加一次插入，則只含插入與刪除的距離可由 m + n - 2 * LCS(source, target) 得到。單位成本替換下，這個公式通常不等於編輯距離：替換一個 不同字元只要一次，而刪除再插入要兩次。使用這個關係前必須先說明操作成本。
追問 5：只判斷「距離是否不超過 k」時如何加速？
長度差超過 k 時立即回傳 false；否則只計算主對角線兩側預算允許的狀態，把帶外儲存格視為不可達， 並在活動前沿已經無法回到預算內時停止。當 k 很小時，這會顯著減少工作；不限制距離時的最壞情況 仍是平方級。
追問 6：真實使用者可見的 Unicode 文字如何處理？
先與產品負責人確定比較單位。依碼點迭代不會拆開代理對，卻仍會拆開部分使用者眼中的單一字元。字素 切分更接近可見字元，Unicode 正規化能讓規範等價的序列一致比較。語系、大小寫折疊、重音和 token 規則都是產品決策。先完成這層前處理，再執行 DP，並用支援語言中的真實範例驗證。
追問 7：能否把兩列再壓成一列？
可以。在覆寫 dp[j] 前，先把舊值保存為下一次使用的左上角；此時 dp[j] 仍表示上方儲存格， dp[j - 1] 已表示本列左側儲存格。這樣只減少常數，不改變漸進空間。面試中兩列版本通常更容易 證明，也較不容易寫錯，除非面試官明確要求原地版本。