当前位置: 首页 > article >正文

力扣hot100 编辑距离 多维DP

Problem: 72. 编辑距离
在这里插入图片描述

文章目录

  • 思路
  • Code

思路

👨‍🏫 参考地址
在这里插入图片描述

在这里插入图片描述

Code

⏰ 时间复杂度: O ( n m ) O(nm) O(nm)
🌎 空间复杂度: O ( n m ) O(nm) O(nm)

class Solution {
	public int minDistance(String s1, String s2)
	{
		int n = s1.length();
		int m = s2.length();
		char[] ss1 = s1.toCharArray();
		char[] ss2 = s2.toCharArray();
		int[][] f = new int[n + 1][m + 1];
//		第一行
		for (int j = 1; j <= m; j++)
			f[0][j] = f[0][j-1] + 1;
//		第一列
		for (int i = 1; i <= n; i++)
			f[i][0] = f[i-1][0] + 1;

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				if (ss1[i - 1] == ss2[j - 1])//说明当前位无需处理
					f[i][j] = f[i - 1][j - 1];
				else//需要处理         当前位采取:     替换           插入           删除   操作数+1           
                    f[i][j] = Math.min(Math.min(f[i - 1][j - 1], f[i][j - 1]), f[i - 1][j]) + 1;
			}
		return f[n][m];
	}
}

http://www.kler.cn/a/226821.html

相关文章:

  • 力扣刷题之旅:启程篇(二)
  • Mac M1使用PD虚拟机运行win10弹出“内部版本已过期立即安装新的windows内部版本”
  • 短剧小程序开发:打造高效、便捷的娱乐体验
  • 好的问卷设计标准:确保数据质量与准确性的关键要素
  • 【Spring实战】33 Spring Boot3 集成 Nacos 配置中心
  • Flink容错机制
  • 2024/1/28CSS学习:基础认知;选择器;文本样式
  • Android ViewPager2 同屏显示左右item
  • Qt实现类似ToDesk顶层窗口 不规则按钮
  • 【Java程序设计】【C00207】基于(JavaWeb+SSM)的宠物领养管理系统(论文+PPT)
  • 前端面试题-JavaScriptl原型,原型链?有什么特点?(2024.2.2)
  • 题目: 有1234个数字, 组成多个互不相同且无重复数字的三位数? 都是多少?
  • 【大数据技术攻关专题】「Apache-Flink零基础入门」手把手+零基础带你玩转大数据流式处理引擎Flink(基础加强+运行原理)
  • 代码随想录算法训练营第二十四天|● 理论基础 ● 77. 组合
  • oracle数据库慢查询SQL
  • 【Delphi】IDE 工具栏错乱恢复
  • 软件工程知识梳理0-概述
  • jQuery前段开发--星级评价和图形跟随指针移动
  • 【报错记录】mybatis映射对应的类没有无参构造引发的问题
  • NUXTJS安装始终报错无法正常运行问题解决