【华为机试】HJ52 计算字符串的编辑距离

发布于：2025-07-17 ⋅ 阅读:(13) ⋅ 点赞:(0)

文章目录

HJ52 计算字符串的编辑距离

描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转变成另一个所需的最少单字符编辑操作次数。被允许的转变包括：

  • 对于任意一个字符串，在任意位置插入一个字符；
  • 对于任意一个字符串，删除任意一个字符；
  • 对于任意一个字符串，替换任意一个字符。

现在，对于给定的字符串 s 和 t，请计算出它们的编辑距离。

输入描述

第一行输入一个长度为 1<=len(s)<=10^3，仅由小写字母组成的字符串 s。
第二行输入一个长度为 1<=len(t)<=10^3，仅由小写字母组成的字符串 t。

输出描述

输出一个整数，表示 s 和 t 的编辑距离。

示例1

输入：
abcdefg
abcdef

输出：
1

说明：
在这个样例中，可以选择将 s 末尾的 ‘g’ 删除。当然，也可以选择在 t 末尾插入 ‘g’。

HJ52 计算字符串的编辑距离

描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转变成另一个所需的最少单字符编辑操作次数。被允许的转变包括：

  • 对于任意一个字符串，在任意位置插入一个字符；
  • 对于任意一个字符串，删除任意一个字符；
  • 对于任意一个字符串，替换任意一个字符。

现在，对于给定的字符串 s 和 t，请计算出它们的编辑距离。

输入描述

第一行输入一个长度为 1<=len(s)<=10^3，仅由小写字母组成的字符串 s。
第二行输入一个长度为 1<=len(t)<=10^3，仅由小写字母组成的字符串 t。

输出描述

输出一个整数，表示 s 和 t 的编辑距离。

示例1

输入：
abcdefg
abcdef

输出：
1

说明：
在这个样例中，可以选择将 s 末尾的 ‘g’ 删除。当然，也可以选择在 t 末尾插入 ‘g’。

解题思路

算法分析

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

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

动态规划状态转移
yes
no
dp_i_j
s_i_minus_1_eq_t_j_minus_1
dp_i_minus_1_j_minus_1
three_operations_min
delete dp_i_minus_1_j plus 1
insert dp_i_j_minus_1 plus 1
replace dp_i_minus_1_j_minus_1 plus 1
min_of_three

状态转移方程

graph LR
    A[状态转移方程] --> B[状态 dp_i_j]
    B --> C{当前字符是否相同}
    C -->|相同| D[继承左上状态 dp_i_减1_j_减1]
    C -->|不同| E[三种操作取最小值]
    E --> F[删除：删除 s_第_i_个字符]
    E --> G[插入：插入 t_第_j_个字符]
    E --> H[替换：将 s_第_i_个字符替换为 t_第_j_个]

算法流程图

flowchart TD
    A[读取字符串 s 和 t] --> B[获取长度：m 是 s 的长度，n 是 t 的长度]
    B --> C[创建 dp 数组，大小为 m 加 1 乘以 n 加 1]
    C --> D[初始化边界条件]
    D --> E[第 0 行：dp_0_j 设为 j，遍历所有 j]
    E --> F[第 0 列：dp_i_0 设为 i，遍历所有 i]
    F --> G[进入双重循环，填充 dp 表]
    G --> H{当前 s 的第 i 个字符是否等于 t 的第 j 个字符}
    H -->|是| I[dp_i_j 设为 dp_i_减1_j_减1]
    H -->|否| J[dp_i_j 设为三种操作中的最小值]
    I --> K{是否循环结束}
    J --> K
    K -->|否| G
    K -->|是| L[返回最终结果 dp_m_n]

DP表格示例

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

graph TD
    A[DP 表格构建过程] --> B[构造完整 DP 数组并填充]
    B --> C[每个 dp_i_j 代表编辑距离]
    C --> D[完成后，查看 dp_3_2 的值]
    D --> E[最终答案：dp_3_2 等于 1]

三种操作详解

graph TD
    A[编辑操作] --> B[插入操作]
    A --> C[删除操作]
    A --> D[替换操作]
    
    B --> E[在字符串 s 中插入字符]
    B --> F[代价：dp_i_j减1 加一]
    
    C --> G[从字符串 s 中删除字符]
    C --> H[代价：dp_i减1_j 加一]
    
    D --> I[将 s 中字符替换为 t 中字符]
    D --> J[代价：dp_i减1_j减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. 空间优化：

    // 只需要两行数组
prev := make([]int, m+1)
curr := make([]int, m+1)

  2. 字符串长度优化：

    // 确保s是较短的字符串
if m > n {
    s, t = t, s
    m, n = n, m
}

  3. 边界条件处理：

    // 空字符串的初始化
dp[0][j] = j  // 需要j次插入
dp[i][0] = i  // 需要i次删除

实际应用场景

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

算法扩展
编辑距离扩展
加权编辑距离
最长公共子序列
最长公共子串
字符串匹配
不同操作不同代价
只允许插入删除
连续字符匹配
模式匹配算法

面试考点

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

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

完整题解代码

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
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布