Saturday, October 24, 2026

中文: 最后一个字符已经匹配，无需操作，问题缩小为子问题 dp[i-1][j-1]

dp[i][j] = dp[i-1][j-1]

dp[i][0] = i   # word2 is empty → delete all i chars from word1
dp[0][j] = j   # word1 is empty → insert all j chars from word2

from functools import lru_cache

def minDistance_memo(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    @lru_cache(maxsize=None)
    def dp(i, j):
        # Base cases: one string exhausted
        if i == 0: return j  # insert j chars from word2
        if j == 0: return i  # delete i chars from word1
        
        if word1[i-1] == word2[j-1]:
            # Characters match — no operation needed
            return dp(i-1, j-1)
        
        # Characters differ — try all 3 operations, pick cheapest
        replace = dp(i-1, j-1)  # replace word1[i-1] with word2[j-1]
        delete  = dp(i-1, j)    # delete word1[i-1]
        insert  = dp(i, j-1)    # insert word2[j-1] after word1[:i]
        
        return 1 + min(replace, delete, insert)
    
    return dp(m, n)

def minDistance_2d(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # dp[i][j] = min ops to transform word1[:i] into word2[:j]
    # Table is (m+1) x (n+1) to accommodate empty string base cases
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base case: transform to/from empty string
    for i in range(m + 1):
        dp[i][0] = i  # delete i chars to get empty string
    for j in range(n + 1):
        dp[0][j] = j  # insert j chars from empty string
    
    # Fill table row by row
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                # Characters match — no operation needed, inherit diagonal
                dp[i][j] = dp[i-1][j-1]
            else:
                # Take cheapest of the 3 operations
                dp[i][j] = 1 + min(
                    dp[i-1][j-1],  # replace
                    dp[i-1][j],    # delete from word1
                    dp[i][j-1]     # insert into word1
                )
    
    return dp[m][n]

def minDistance_optimized(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # prev[j] represents dp[i-1][j] from the 2D version
    prev = list(range(n + 1))  # base case: dp[0][j] = j
    
    for i in range(1, m + 1):
        # curr[j] = dp[i][j] for the current row
        curr = [0] * (n + 1)
        curr[0] = i  # base case: dp[i][0] = i
        
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                # Match: take diagonal (prev row, prev column)
                curr[j] = prev[j-1]
            else:
                curr[j] = 1 + min(
                    prev[j-1],  # replace  (diagonal in 2D)
                    prev[j],    # delete   (cell above in 2D)
                    curr[j-1],  # insert   (cell left in 2D)
                )
        
        prev = curr  # shift rows
    
    return prev[n]

# ❌ WRONG: missing base cases
dp = [[0] * n for _ in range(m)]

# ✅ CORRECT: includes empty string rows/columns
dp = [[0] * (n + 1) for _ in range(m + 1)]

# ❌ WRONG: only creates zero table
dp = [[0] * (n+1) for _ in range(m+1)]
# Missing: dp[i][0] = i and dp[0][j] = j !

# ✅ CORRECT
for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j

# ❌ WRONG
if word1[i] == word2[j]:  # IndexError when i=m

# ✅ CORRECT: i is 1-indexed in dp, 0-indexed in string
if word1[i-1] == word2[j-1]:

中文: 题目默认 insert / delete / replace 各算一步操作，代价相同。
如果题目改成代价不同（比如 insert=2, delete=1），只需修改 +1 的部分。

English: All three operations cost 1. If costs differ (weighted edit distance),
just change the +1 to +cost for each operation type.

minDistance("", "ros")  # → 3 (insert 3 chars)
minDistance("horse", "")  # → 5 (delete 5 chars)
minDistance("", "")  # → 0

# All handled correctly by base case initialization

$ git diff HEAD~1 HEAD -- file.py

# Simplified spell checker using edit distance
def suggest_corrections(word: str, dictionary: list[str], max_dist: int = 2) -> list[str]:
    return [
        w for w in dictionary
        if minDistance(word, w) <= max_dist
    ]

suggest_corrections("recieve", ["receive", "relieve", "retrieve"])
# → ["receive"]  (edit distance = 1: swap i and e)

{
  "query": {
    "fuzzy": {
      "name": {
        "value": "recieve",
        "fuzziness": 1   ← max edit distance of 1
      }
    }
  }
}

A: Time is O(m×n) — we compute each of the m×n cells once.
   Space is O(m×n) for the 2D table, reducible to O(n) by keeping
   only the current and previous rows. We can even do O(min(m,n)) by
   iterating over the shorter string in the inner loop.

中文: 时间 O(m×n) 无法进一步优化（每个子问题至少算一次）。
      空间可从 O(m×n) 优化到 O(n)，只保留当前行和上一行。

# Backtrack through the DP table from dp[m][n] to dp[0][0]
def reconstruct_ops(word1, word2, dp):
    ops = []
    i, j = len(word1), len(word2)
    while i > 0 or j > 0:
        if i > 0 and j > 0 and word1[i-1] == word2[j-1]:
            i -= 1; j -= 1  # no op, diagonal
        elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
            ops.append(f"replace word1[{i-1}] with '{word2[j-1]}'")
            i -= 1; j -= 1
        elif i > 0 and dp[i][j] == dp[i-1][j] + 1:
            ops.append(f"delete word1[{i-1}]='{word1[i-1]}'")
            i -= 1
        else:
            ops.append(f"insert '{word2[j-1]}' at position {i}")
            j -= 1
    return list(reversed(ops))

# 中文: 从右下角反推，每步判断当前值来自哪个方向（对角/上/左），还原操作序列。

A: They're related! Edit distance and LCS both use a 2D DP table with
   similar recurrence. The connection:
   
   editDistance(s1, s2) = m + n - 2 * LCS(s1, s2)
   
   (Where LCS length tells you the max chars you DON'T need to change)

中文: 编辑距离和 LCS 本质相通。LCS 越长，需要修改的字符越少。
      如果操作只有 insert/delete（无 replace），公式成立。
      有 replace 时稍有不同，但直觉相同。

# Just change the constants:
def weightedEditDistance(word1, word2, ins=2, dlt=1, rep=3):
    # ...same structure, replace +1 with +ins, +dlt, +rep
    dp[i][j] = min(
        dp[i-1][j-1] + rep,  # replace
        dp[i-1][j]   + dlt,  # delete
        dp[i][j-1]   + ins,  # insert
    )
    
# 中文: 改变代价系数即可。这也是生物信息学中 alignment scoring matrix 的基础。

A: Edit distance treats every character equally — it doesn't understand
   that 'o' and '0' look similar, or that keyboard proximity matters.
   
   Better alternatives:
   - Jaro-Winkler: optimized for names/short strings (rewards prefix matches)
   - BK-trees: efficient data structure for edit distance lookups at scale
   - Word-level edit distance: for NLP, compare words not characters
   - Phonetic distance: Soundex/Metaphone for audio similarity

中文: 编辑距离把所有字符等价对待，不考虑视觉相似性、发音相似性或键盘邻近性。
      实际系统通常组合多种相似度指标，而非单用编辑距离。

# i=5 (word1[4]='e'), j=3 (word2[2]='s')
# 'e' != 's' → take minimum of:
#   dp[4][2] (replace) = 3
#   dp[4][3] (delete)  = 2   ← minimum
#   dp[5][2] (insert)  = 4
# dp[5][3] = 1 + 2 = 3  ✓

# Verify dp[4][3]: i=4 (word1[3]='s'), j=3 (word2[2]='s')
# 's' == 's' → dp[3][2] = 2  ✓

# Verify dp[3][2]: i=3 (word1[2]='r'), j=2 (word2[1]='o')
# 'r' != 'o' → 1 + min(dp[2][1]=2, dp[2][2]=1, dp[3][1]=2) = 1+1 = 2  ✓

两串对比找距离，dp 表格填满你
字符相同取对角，字符不同三选一
删插替换各 +1，右下角就是答案