代码随想录算法训练营Day55|LC392 判断子序列LC115 不同的子序列LC583 两个字符串的删除操作

本文主要是介绍代码随想录算法训练营Day55|LC392 判断子序列LC115 不同的子序列LC583 两个字符串的删除操作,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一句话总结:115有点难想转移方程。

原题链接:392 判断子序列

题比较简单,dp方法不做一一分析,代码如下:

class Solution {public boolean isSubsequence(String s, String t) {int m = s.length(), n = t.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = dp[i][j - 1];}}return dp[m][n] == m ? true : false;}
}

 

原题链接: 115 不同的子序列

 

本题较难。按dp五部曲分析如下:

  1. 确定dp数组及下标的含义:以s[i - 1]结尾的s子序列中出现的以t[j - 1]为结尾的t的子序列的个数;
  2. 确定状态转移方程:s[i - 1] == t[j - 1]时,dp[i][j]由两种情况的和而来:即dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j],s[i - 1] != t[j - 1]时,dp[i][j]则只有一种转移情况:dp[i][j] = dp[i - 1][j];
  3. dp数组的初始化:对于dp[i][0],由于t的空串为任意字符串的子序列,因此dp[i][0]= 1。同时,对于dp[0][j](0 < j < n),由于s的空串除空串外不可能有任何子序列,因此dp[0][j] = 0;
  4. 确定遍历顺序:从上面方程的推导过程来看,一定是从上往下从左往右的;
  5. 举例推导:略。

以下是代码:

class Solution {static final int MOD = (int) 1e9 + 7;public int numDistinct(String s, String t) {char[] cs  = s.toCharArray(), ct = t.toCharArray();int m = s.length(), n = t.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; ++i) {dp[i][0] = 1;}for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (cs[i - 1] == ct[j - 1]) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;else dp[i][j] = dp[i - 1][j] % MOD;}}return dp[m][n] % MOD;}
}

这篇关于代码随想录算法训练营Day55|LC392 判断子序列LC115 不同的子序列LC583 两个字符串的删除操作的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907761

相关文章

Linux使用fdisk进行磁盘的相关操作

《Linux使用fdisk进行磁盘的相关操作》fdisk命令是Linux中用于管理磁盘分区的强大文本实用程序,这篇文章主要为大家详细介绍了如何使用fdisk进行磁盘的相关操作,需要的可以了解下... 目录简介基本语法示例用法列出所有分区查看指定磁盘的区分管理指定的磁盘进入交互式模式创建一个新的分区删除一个存

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1,PDF转Word2,PDF转Excel三、前端页面效果展示总结一

java脚本使用不同版本jdk的说明介绍

《java脚本使用不同版本jdk的说明介绍》本文介绍了在Java中执行JavaScript脚本的几种方式,包括使用ScriptEngine、Nashorn和GraalVM,ScriptEngine适用... 目录Java脚本使用不同版本jdk的说明1.使用ScriptEngine执行javascript2.

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中,常将INI文件作为配置文件,用于存储应用程序的

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log

Java操作ElasticSearch的实例详解

《Java操作ElasticSearch的实例详解》Elasticsearch是一个分布式的搜索和分析引擎,广泛用于全文搜索、日志分析等场景,本文将介绍如何在Java应用中使用Elastics... 目录简介环境准备1. 安装 Elasticsearch2. 添加依赖连接 Elasticsearch1. 创

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种:使用wm_concat() + distinct去重聚合第二种:使用listagg,