package main

import (
	"fmt"
)

func main() {
	var s, t string
	fmt.Scanln(&s)
	fmt.Scanln(&t)

	result := editDistance(s, t)
	fmt.Println(result)
}

// editDistance 计算两个字符串的编辑距离
// 使用动态规划算法，时间复杂度O(mn)，空间复杂度O(mn)
func editDistance(s, t string) int {
	m, n := len(s), len(t)

	// dp[i][j] 表示 s[0:i] 和 t[0:j] 的编辑距离
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// 初始化边界条件
	// s为空字符串时，需要插入t的所有字符
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	// t为空字符串时，需要删除s的所有字符
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}

	// 动态规划填表
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] {
				// 字符相同，不需要操作
				dp[i][j] = dp[i-1][j-1]
			} else {
				// 字符不同，取三种操作的最小值
				dp[i][j] = min(
					dp[i-1][j]+1,   // 删除s[i-1]
					dp[i][j-1]+1,   // 插入t[j-1]
					dp[i-1][j-1]+1, // 替换s[i-1]为t[j-1]
				)
			}
		}
	}

	return dp[m][n]
}

// 空间优化版本：只使用O(min(m,n))空间
func editDistanceOptimized(s, t string) int {
	m, n := len(s), len(t)

	// 确保s是较短的字符串，优化空间使用
	if m > n {
		s, t = t, s
		m, n = n, m
	}

	// 只需要两行：当前行和上一行
	prev := make([]int, m+1)
	curr := make([]int, m+1)

	// 初始化第一行
	for i := 0; i <= m; i++ {
		prev[i] = i
	}

	// 逐行计算
	for j := 1; j <= n; j++ {
		curr[0] = j // 边界条件

		for i := 1; i <= m; i++ {
			if s[i-1] == t[j-1] {
				curr[i] = prev[i-1]
			} else {
				curr[i] = min(
					prev[i]+1,   // 删除
					curr[i-1]+1, // 插入
					prev[i-1]+1, // 替换
				)
			}
		}

		// 交换prev和curr
		prev, curr = curr, prev
	}

	return prev[m]
}

// 递归+记忆化版本（展示不同实现思路）
func editDistanceMemo(s, t string) int {
	m, n := len(s), len(t)
	memo := make([][]int, m+1)
	for i := range memo {
		memo[i] = make([]int, n+1)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}

	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		// 边界条件
		if i == 0 {
			return j
		}
		if j == 0 {
			return i
		}

		// 记忆化
		if memo[i][j] != -1 {
			return memo[i][j]
		}

		if s[i-1] == t[j-1] {
			memo[i][j] = dfs(i-1, j-1)
		} else {
			memo[i][j] = min(
				dfs(i-1, j)+1,   // 删除
				dfs(i, j-1)+1,   // 插入
				dfs(i-1, j-1)+1, // 替换
			)
		}

		return memo[i][j]
	}

	return dfs(m, n)
}

// min 返回三个数中的最小值
func min(a, b, c int) int {
	if a <= b && a <= c {
		return a
	}
	if b <= c {
		return b
	}
	return c
}

// 用于两个数的min函数
func min2(a, b int) int {
	if a < b {
		return a
	}
	return b
}

解题思路

算法分析

这道题是经典的动态规划问题——编辑距离（Levenshtein距离）。主要涉及：

  1. 状态定义：dp[i][j]表示s[0:i]和t[0:j]的编辑距离
  2. 状态转移：根据字符是否相同选择最优操作
  3. 边界处理：空字符串的初始化
  4. 空间优化：滚动数组优化空间复杂度

动态规划状态转移

graph TD
    A[dp[i][j]] --> B{s[i-1] == t[j-1]?}
    B -->|是| C[dp[i-1][j-1]]
    B -->|否| D[三种操作取最小值]
    
    D --> E[删除: dp[i-1][j] + 1]
    D --> F[插入: dp[i][j-1] + 1]
    D --> G[替换: dp[i-1][j-1] + 1]
    
    E --> H[min三者]
    F --> H
    G --> H

状态转移方程

graph LR
    A[状态转移方程] --> B[dp[i][j]]
    B --> C{字符是否相同}
    C -->|相同| D[dp[i-1][j-1]]
    C -->|不同| E[min操作]
    E --> F[删除s[i-1]]
    E --> G[插入t[j-1]]
    E --> H[替换为t[j-1]]

算法流程图

flowchart TD
    A[读取字符串s和t] --> B[获取长度m=len(s), n=len(t)]
    B --> C[创建dp数组 (m+1)×(n+1)]
    C --> D[初始化边界条件]
    D --> E[dp[0][j] = j for all j]
    E --> F[dp[i][0] = i for all i]
    F --> G[双重循环填表]
    G --> H{s[i-1] == t[j-1]?}
    H -->|是| I[dp[i][j] = dp[i-1][j-1]]
    H -->|否| J[dp[i][j] = min三种操作]
    I --> K{循环结束?}
    J --> K
    K -->|否| G
    K -->|是| L[返回dp[m][n]]

DP表格示例

以s="abc", t="ab"为例：

graph TD
    A[DP表格构建过程]
    A --> B[
        "   ε  a  b
         ε  0  1  2
         a  1  0  1
         b  2  1  0
         c  3  2  1"
    ]
    B --> C[最终答案: dp[3][2] = 1]

三种操作详解

graph TD
    A[编辑操作] --> B[插入操作]
    A --> C[删除操作]
    A --> D[替换操作]
    
    B --> E[在s中插入字符]
    B --> F[代价: dp[i][j-1] + 1]
    
    C --> G[从s中删除字符]
    C --> H[代价: dp[i-1][j] + 1]
    
    D --> I[替换s中字符]
    D --> J[代价: dp[i-1][j-1] + 1]

代码实现思路

  1. 基础DP版本：二维数组存储所有状态时间复杂度O(mn)，空间复杂度O(mn)易于理解和调试
  2. 空间优化版本：滚动数组优化空间时间复杂度O(mn)，空间复杂度O(min(m,n))适用于大规模数据
  3. 记忆化递归版本：自顶向下的思考方式代码更直观，容易理解递归关系适合面试讲解

时间复杂度分析

基础DP

O(mn)

O(mn)

经典实现

空间优化

O(mn)

O(min(m,n))

节省空间

记忆化递归

O(mn)

O(mn)

易于理解

关键优化技巧

  1. 空间优化：
  2. 字符串长度优化：
  3. 边界条件处理：

实际应用场景

  1. 文本相似度计算：搜索引擎的模糊匹配
  2. 拼写检查：单词纠错功能
  3. DNA序列比对：生物信息学中的序列分析
  4. 版本控制：Git中的文件差异比较
  5. 自然语言处理：文本相似度度量

算法扩展

graph TD
    A[编辑距离扩展] --> B[加权编辑距离]
    A --> C[最长公共子序列]
    A --> D[最长公共子串]
    A --> E[字符串匹配]
    
    B --> F[不同操作不同代价]
    C --> G[只允许插入删除]
    D --> H[连续字符匹配]
    E --> I[模式匹配算法]

面试考点

  1. 状态定义能力：正确定义DP状态
  2. 状态转移推导：理解三种操作的含义
  3. 边界条件处理：空字符串的初始化
  4. 空间优化思维：滚动数组的使用
  5. 实际应用理解：算法的实际价值

测试用例分析

graph TD
    A[测试用例分析] --> B[基础用例: abcdefg vs abcdef]
    A --> C[相同字符串: abc vs abc]
    A --> D[完全不同: abc vs xyz]
    A --> E[空字符串: "" vs abc]
    
    B --> F[结果: 1，删除g]
    C --> G[结果: 0，无需操作]
    D --> H[结果: 3，全部替换]
    E --> I[结果: 3，全部插入]

这个问题是动态规划的经典应用，展示了如何将复杂问题分解为子问题，并通过状态转移方程求解最优解。编辑距离算法在实际工程中有广泛应用，是面试中的高频考点。