編輯距離

Vibe Prompt

「幫我實作編輯距離計算：'kitten' → 'sitting' 需要幾步？輸出 dp 表格與最佳操作序列。」

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

print(f"kitten → sitting: {edit_distance('kitten', 'sitting')} 步")
print(f"Vibe → Vibes: {edit_distance('Vibe', 'Vibes')} 步")

# 實戰：自動拼寫建議
def spell_check(word, dictionary):
    return min(dictionary, key=lambda w: edit_distance(word, w))

dict_words = ["coding", "coding", "vibe", "tutor", "python", "algorithm"]
print(f"您是不是想說: {spell_check('codng', dict_words)}?")