Leetcode——最长公共子序列 / 最长公共子串

article/2025/9/20 13:17:21

1. 最长公共子序列

在这里插入图片描述

（1）DFS暴搜（超时）

class Solution{public static int longestCommonSubsequence(String text1, String text2) {char[] t1Chars = text1.toCharArray();char[] t2Chars = text2.toCharArray();return process(t1Chars, t2Chars, t1Chars.length, t2Chars.length);}//返回text1长度x，text2长度为y情况下的最长公共子序列长度private static int process(char[] t1Chars, char[] t2Chars, int x, int y) {if (x == 0 || y == 0) return 0;return t1Chars[x-1] == t2Chars[y-1] ? (process(t1Chars, t2Chars, x-1, y-1) + 1): Math.max(process(t1Chars, t2Chars, x-1, y), process(t1Chars, t2Chars, x, y-1));}
}

（2）记忆化DFS

暴力递归慢就慢在对于一个位置值的重复求解，比如说process(3,3),在(4,4)的时候可能求一次，在(3,4)可能又求一次…等等，反正会被求到很多次

  • 记忆化：针对性的优化：使用缓存，将求过的值进行保存，下次直接使用
class Solution{public  int longestCommonSubsequence(String text1, String text2) {char[] t1Chars = text1.toCharArray();char[] t2Chars = text2.toCharArray();HashMap<String,Integer> cache = new HashMap<>();return process2(t1Chars, t2Chars, t1Chars.length, t2Chars.length, cache);}private  int process2(char[] t1Chars, char[] t2Chars, int x, int y, HashMap<String, Integer> cache) {//存储当前text1长度x，text2长度为y情况下的最长公共子序列长度，下次重复递归时可以直接使用String key = x + "_" + y;if (cache.containsKey(key)) return cache.get(key);if (x == 0 || y == 0) {cache.put(key,0);return 0;}int result = t1Chars[x - 1] == t2Chars[y - 1] ? (process2(t1Chars, t2Chars, x - 1, y - 1,cache) + 1): Math.max(process2(t1Chars, t2Chars, x - 1, y,cache), process2(t1Chars, t2Chars, x, y - 1,cache));//存储当前计算的text1长度x，text2长度为y情况下的最长公共子序列长度cache.put(key,result);return result;}
}

（3）DP

  • 单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果
  • 当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果
  • 本题可以定义 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。
  • 注：text1[0:i-1] 表示的是 text1 的 第 0 个元素到第 i - 1 个元素，两端都包含）
    之所以 dp[i][j] 的定义不是 text1[0:i] 和 text2[0:j] ，是为了方便当 i = 0 或者 j = 0 的时候，dp[i][j]表示的为空字符串和另外一个字符串的匹配，这样 dp[i][j] 可以初始化为 0。
class Solution {public int longestCommonSubsequence(String text1, String text2) {int len1 = text1.length();int len2 = text2.length();if (text1 == null || text2 == null || len1 < 1 || len2 < 1) return 0;//定义 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。 所以需要 + 1//之所以 dp[i][j] 的定义不是 text1[0:i] 和 text2[0:j] ，是为了方便当 i = 0 或者 j = 0 的时候，//dp[i][j]表示的为空字符串和另外一个字符串的匹配，这样 dp[i][j] 可以初始化为 0。int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; ++i) {for (int j = 1; j <= len2; ++j) {//由于当 i 和 j 取值为 0 的时候，dp[i][j] = 0，而 dp 数组本身初始化就是为 0，所以，直接让 i 和 j 从 1 开始遍历//遍历的结束应该是字符串的长度为 len(text1) 和 len(text2)。if (text1.charAt(i - 1) == text2.charAt(j - 1)) {//两个子字符串的最后一位相等，所以最长公共子序列又增加了 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {//两个子字符串的最后一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[len1][len2];}
}

2. 最长公共子串（最长重复数组）

假如有两个字符串，s1=“people"和s2=“eplm”，我们要求他俩最长的公共子串。我们一眼就能看出他们的最长公共子串是"pl”，长度是2。但如果字符串特别长的话就不容易那么观察了。

（1）暴力

public int getLCS(String s, String s2) {if (s == null || t == null) {return 0;}int l1 = s1.length();int l2 = s2.length();int res = 0;for (int i = 0; i < l1; i++) {for (int j = 0; j < l2; j++) {int m = i;int n = j;int len = 0;while (m < l1 && n < l2 && s1.charAt(m) == s2.charAt(n)) {len++;m++;n++;}res = Math.max(res, len);}}return res;}

（2）DP

  • 用一个二维数组dp[i][j]表示 第一个字符串前 i 个字符 和 第二个字符串前 j 个字符 组成的最长公共字符串的长度。

  • 那么我们在计算dp[i][j]的时候，我们首先要判断s1.charAt(i)是否等于s2.charAt(j)：

    • 如果不相等，说明当前字符无法构成公共子串，所以dp[i][j]=0。
    • 如果相等，说明可以构成公共子串，我们还要加上他们前一个字符构成的最长公共子串长度，也就是dp[i-1][j-1]。所以我们很容易找到递推公式

  • 递推公式为：

if(s1.charAt(i) == s2.charAr(j))dp[i][j] = dp[i-1][j-1] + 1;
elsedp[i][j] = 0;

具体代码：

public static int maxLong(String str1, String str2) {if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)return 0;int max = 0;// +1是为了防止边界条件判断 和 减少初始化当 i 或 j 等于 0 时，初始化子串就是为0，初始化数组也是为0int[][] dp = new int[str1.length() + 1][str2.length() + 1];for (int i = 1; i <= str1.length(); i++) {for (int j = 1; j <= str2.length(); j++) {if (str1.charAt(i - 1) == str2.charAt(j - 1))dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = 0;//最大值不一定出现在数组的最后一个位置，所以要用一个临时变量记录下来。max = Math.max(max, dp[i][j]);	}}return max;
}

（3）DP优化

public static int maxLong(String str1, String str2) {if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0)return 0;int max = 0;int[] dp = new int[str2.length() + 1];for (int i = 1; i <= str1.length(); i++) {//使用的倒序的方式，这是因为dp数组后面的值会依赖前面的值，而前面的值不依赖后面的值，所以后面的值先修改对前面的没影响，但前面的值修改会对后面的值有影响，所以这里要使用倒序的方式。for (int j = str2.length(); j >= 1; j--) {if (str1.charAt(i - 1) == str2.charAt(j - 1))dp[j] = dp[j - 1] + 1;elsedp[j] = 0;max = Math.max(max, dp[j]);}}return max;
}

http://chatgpt.dhexx.cn/article/bC4BTJ6j.shtml

相关文章

C语言----最长公共子串(动态规划)

C语言----最长公共子串(动态规划)

定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j]&#xff0c;也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串&#xff0c;我们首先需要判断这两个字符是否相等。 如果不相等&#x…
阅读更多...
最长公共子串

最长公共子串

最长公共子串 原题链接&#xff1a;https://www.lintcode.com/problem/79 题目 给出两个字符串&#xff0c;找到最长公共子串&#xff0c;并返回其长度。 子串的字符应该连续的出现在原字符串中&#xff0c;这与子序列有所不同。 样例 样例 1&#xff1a; 输入&#xff1a…
阅读更多...
动态规划——最长公共子串，没有比这更通俗易懂的了

动态规划——最长公共子串，没有比这更通俗易懂的了

前言 动态规划是大厂的热门考点&#xff0c;其中最长公共子串与最长公共子序列这两道题出现得尤其频繁&#xff0c;这两道题其实有挺多变种&#xff0c;很适合考察侯选人对动态规划的掌握情况&#xff0c;今天我们就先来看看如何求解最长公共子串&#xff0c;图文并茂&#xff…
阅读更多...
SQL中字符串拼接方法（MySQL，SQLServer）

SQL中字符串拼接方法（MySQL，SQLServer）

1 SQLServer &#xff08;1&#xff09;用号实现字符串拼接 select 123456; &#xff08;2&#xff09;用concat()内置函数实现字符串拼接 注&#xff1a;SQLServer 2012及更高版本才支持conconcat()函数。 select concat(123,456);//两个字符串拼接 2 MySQL &#xff0…
阅读更多...
mysql 使用group by分组后对某个字段值拼接成字符串方法，一般人都不知道！

mysql 使用group by分组后对某个字段值拼接成字符串方法，一般人都不知道！

只需要使用GROUP_CONCAT函数可以在使用groupby分组后&#xff0c;将某个字段的值进行拼接合并 使用示例&#xff1a; 数据表&#xff1a;testTb 使用 GROUP_CONCAT函数来实现&#xff0c;我们的sql可以这样写 Select albumId,GROUP_CONCAT(name) from testTb group by albumI…
阅读更多...
MySql查询结果拼接成字符串

MySql查询结果拼接成字符串

背景&#xff1a;做SQL查询时会经常需要&#xff0c;把查询的结果拼接成一个字符串。 解决方法&#xff1a; 通过 group_concat 函数 1.正常查询 如下: select id result from ctp_enum_item limit 100; 2.拼接结果 如下 select group_concat("",id,"") r…
阅读更多...
MySQL 字符串拼接

MySQL 字符串拼接

在Mysql 数据库中存在两种字符串连接操作.具体操作如下 一. 语法: 1. CONCAT(string1,string2,…) 说明 : string1,string2代表字符串,concat函数在连接字符串的时候&#xff0c;只要其中一个是NULL,那么将返回NULL 例1: 例2: 2. CONCAT_WS(separator,str1,str2,...) 说明 : …
阅读更多...
MySQL字符串合并

MySQL字符串合并

MySQL有几种合并字符串的方式&#xff0c;下面来介绍一下 CONCAT函数 concat(str1, str2,...) 返回结果为连接参数产生的字符串&#xff0c;如果有任何一个参数为null&#xff0c;则返回值为null。 mysql> select concat(www,MySQL,substringIndex,com) ----------------…
阅读更多...
mysql concat字符串拼接函数使用

mysql concat字符串拼接函数使用

目录 1、concat 2、concat_ws 3、group_concat 1、concat select CONCAT(h,e,llo) from dual; 2、concat_ws 指定分隔符进行字符串的拼接 select CONCAT_WS(_,h,e,llo) from dual;3、group_concat 用法&#xff1a; group_concat( [distinct] {要连接的字段}[order by …
阅读更多...
MySQL如何分组拼接字符串？

MySQL如何分组拼接字符串？

上一篇文章 跨表更新&#xff0c;看到自己写的SQL像个憨憨 写了关于跨表个更新的内容。一年过的很快&#xff0c;文中后来的两位员工 馮大 和 馮二 也要面对无情的 KPI 考核了&#xff0c;他们工作干的很不错&#xff0c;performance 分别是 4 和 5 新需求来了&#xff0c;静悄…
阅读更多...
MySQL字符串拼接函数

MySQL字符串拼接函数

MySQL字符串拼接函数有以下三个&#xff1a; CONCATCONCAT_WSGROUP_CONCAT 1.CONCAT 说明 对指定字符进行拼接 语法 CONCAT(str1,str2,...) 语法说明&#xff1a; CONCAT(字符1,字符2,...) 实例 SELECT CONCAT(this ,is ,a ,demo) AS result FROM DUAL2.CONCAT_WS 说明 …
阅读更多...
mysql 实现字符串的拼接

mysql 实现字符串的拼接

在Mysql 数据库中存在两种字符串连接操作.具体操作如下 一. 语法: 1. CONCAT(string1,string2,…) 说明 : string1,string2代表字符串,concat函数在连接字符串的时候&#xff0c;只要其中一个是NULL,那么将返回NULL 例1: 例2: 2. CONCAT_WS(separator,str1,str2,...) 说明 :…
阅读更多...
MySQL 字符串拼接 - 多种字符串拼接实战案例

MySQL 字符串拼接 - 多种字符串拼接实战案例

本文首发&#xff1a;MySQL 字符串拼接 - 多种字符串拼接实战案例 - 卡拉云 MySQL 字符串拼接可以使多个字段的值组成一个集合&#xff0c;不仅可以拼接字符串与字符串、空格、特殊符号甚至可以拼接中文文本&#xff0c;方便我们在不同场景下应用。 本教详细讲解 CONCAT() 和…
阅读更多...
MySQL字符串拼接的两种方式

MySQL字符串拼接的两种方式

第一种&#xff1a; MySQL自带语法Concat(string1,string2,string3...)&#xff0c;此处是直接把string1和string2等等的字符串拼接起来&#xff08;无缝拼接哦&#xff09; 说明&#xff1a;此方法在拼接的时候如果有一个值为NULL&#xff0c;则返回NULL select concat(&qu…
阅读更多...
MySQL字符串拼接(函数)

MySQL字符串拼接(函数)

最近帮助处理数据,需要批量更新数据,遂上网查了查方法,在此记录一下。我的原始数据如下: 一.CONCAT()函数 说明 : CONCAT(string1,string2,string3...)&#xff0c;此处是直接把string1、string2和string3等等的字符串无缝拼接起来&#xff0c;返回结果为连接参数产生的字符…
阅读更多...
MYSql-字符串拼接

MYSql-字符串拼接

一、MySQL自带字符串拼接函数 CONCAT 字符串拼接CONCAT_WS 指定字符串分割拼接字符串拼接 ① 语法&#xff1a;CONCAT(str1,str2…) 解释&#xff1a;concat 拼接 str1和str2字符串, 省略号....代表可以多个字符串拼接 示例&#xff1a; SELECT CONCAT("hello&quo…
阅读更多...
MySQL字符串拼接concat()、分组拼接字符串group_concat()

MySQL字符串拼接concat()、分组拼接字符串group_concat()

MySQL拼接 一、经典拼接concat(x,x,....)二、分隔符拼接CONCAT_WS(separator,str1,str2,...)三、分组拼接GROUP_CONCAT(expr) 一、经典拼接concat(x,x,....) 用法案例&#xff1a; SELECTconcat( 字符串, 拼接, &#xff0c;啥都可以, 嘿嘿 ) AS concats FROM DUAL注意&…
阅读更多...
SQL 拼接字符串

SQL 拼接字符串

不同的数据库&#xff0c;相应的字符串拼接方式不同&#xff0c;下面进行详细讲解。 一、MySQL字符串拼接 1、CONCAT函数 语法格式&#xff1a;CONCAT(char c1, char c2, …, char cn) &#xff0c;其中char代表字符串&#xff0c;定长与不定长均可以 连接两个字符串 sele…
阅读更多...
Mysql之字符串拼接

Mysql之字符串拼接

mysql字符串拼接 两种方式&#xff0c;第一种&#xff0c;使用 “” 进行拼接&#xff08;错误的方法&#xff09;&#xff0c; 第二种使用Mysql函数CONCAT()等函数。 使用 “” 使用“”进行对数据是加减。不能进行拼接 拼接用法&#xff1a; 数据表&#xff1a; 错误写法&am…
阅读更多...
mysql中的实现字段或字符串拼接的三种方式

mysql中的实现字段或字符串拼接的三种方式

一、CONCAT函数 concat函数是将多个字段或字符串拼接为一个字符串&#xff1b;但是字符串之间没有任何分隔。 concat函数官方介绍 -- CONCAT函数的语法如下&#xff1a; CONCAT(str1,str2,...) 1.1、拼接非空字段或字符串 SELECT CONCAT(字段1,字段2,字段3,...) from 表名;-- 拼…
阅读更多...
推荐文章

Copyright @ 2022~2023