萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣1143题-最长公共子序列-题解

发表于 2021-04-17 | 分类于 力扣刷题 | 0 | 阅读次数 305

题目描述

给定两个字符串text1和text2,返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列,返回0。

一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,"ace"是"abcde"的子序列,但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

样例

  1. 示例 1:
    输入:text1 = "abcde", text2 = "ace"
    输出:3
    解释:最长公共子序列是"ace",它的长度为3。

  2. 示例 2:
    输入:text1 = "abc", text2 = "abc"
    输出:3
    解释:最长公共子序列是"abc",它的长度为3。

  3. 示例 3:
    输入:text1 = "abc", text2 = "def"
    输出:0
    解释:两个字符串没有公共子序列,返回0。

题目评估

知识点:动态规划
难度:中等

分析

本题可以使用动态规划来解。
当text1[i]=text2[j]时,text1[0..i]和text2[0..j]的最大公共子序列长度可由text1[0..i-1]和text2[0..j-1]的最大公共子序列长度+1获得。
当text1[i]!=text2[j]时,text1[0..i]和text2[0..j]的最大公共子序列长度为
Max(text1[0..i-1]和text2[0..j]的最大公共子序列长度, text1[0..i]和text2[0..j-1]的最大公共子序列长度)。
由此可以得到转移公式(其中dp数组记录长度)
image.png

图解:
leetcode-1143-img

Java代码题解

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
		
    	if (text1.length() == 0 || text2.length() == 0) {  // 如果任意字符串长度为0直接返回0
    		return 0;
    	}
    	
    	// text1的长度为text1.length() = n
    	// text2的长度为text2.length() = m
    	// 开辟一个n+1行m+1列的数组
    	int[][] dp = new int[text1.length() + 1][text2.length() + 1];
    	
    	for (int i = 1; i < dp.length; i++) {  // 遍历text1的长度为i的子串text1[0..i]
			char ch1 = text1.charAt(i - 1);  // 取出当前字符text1[i]
    		for (int j = 1; j < dp[i].length; j++) {  // 遍历text2的长度为j的子传text2[0..j]
				char ch2 = text2.charAt(j - 1);  // 去除当前字符text2[j]
				if (ch1 == ch2) {  
					// 如果当前字符text1[i]=text2[j]
					// text1[0..i]与text2[0..j]的最大公共子序列的长度 等于 text1[0..i-1]与text2[0..j-1]的最大公共子序列的长度+1
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					// 如果当前字符text1[i]!=text2[j]
					// text1[0..i-1]与text2[0..j]的最大公共子序列的长度,text1[0..i]与text2[0..j-1]的最大公共子序列的长度
					// 哪个大,哪个就是text1[0..i]与text2[0..j]的最大公共子序列的长度
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}
    	return dp[dp.length - 1][dp[0].length - 1];  // 返回dp[n][m]
    }
}
力扣1143题

复杂度分析

设n是text1的长度,m为text2的长度,则时间复杂度为O(nm)。
因为创建了一个n+1行m+1列的数组,空间复杂度为O(nm)。

# 算法 # 程序设计 # 动态规划
力扣17题-电话号码的字母组合-回溯算法题解
力扣516题-最长回文子序列-动态规划题解
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持