首页 > 其他分享 >【月度刷题计划同款】经典 LCS 问题

【月度刷题计划同款】经典 LCS 问题

时间:2023-06-18 18:38:01浏览次数:33  
标签:LCS strs 复杂度 序列 字符串 同款 长度 刷题

题目描述

这是 LeetCode 上的 522. 最长特殊序列 II ,难度为 中等

Tag : 「LCS」、「最长公共子序列」、「序列 DP」、「枚举」、「动态规划」

给定字符串列表 strs,返回其中 最长的特殊序列 。如果最长特殊序列不存在,返回 【月度刷题计划同款】经典 LCS 问题_复杂度

特殊序列 定义如下:该序列为某字符串 独有的子序列(即不能是其他字符串的子序列)。

s 的 子序列可以通过删去字符串 s 中的某些字符实现。

  • 例如,"abc" 是 "aebdc" 的子序列,因为您可以删除 "aebdc" 中的下划线字符来得到 "abc" 。"aebdc" 的子序列还包括 "aebdc""aeb" 和 "" (空字符串)。

示例 1:

输入: strs = ["aba","cdc","eae"]

输出: 3

示例 2:

输入: strs = ["aaa","aaa","aa"]

输出: -1

提示:

  • 【月度刷题计划同款】经典 LCS 问题_算法_02
  • 【月度刷题计划同款】经典 LCS 问题_子序列_03
  • strs[i] 只包含小写英文字母

LCS

strs 数组长度为 【月度刷题计划同款】经典 LCS 问题_子序列_04,单个 【月度刷题计划同款】经典 LCS 问题_后端_05 的最大长度 【月度刷题计划同款】经典 LCS 问题_后端_06。其中 【月度刷题计划同款】经典 LCS 问题_子序列_04 数据范围为 【月度刷题计划同款】经典 LCS 问题_Java_08【月度刷题计划同款】经典 LCS 问题_后端_06 数据范围为 【月度刷题计划同款】经典 LCS 问题_子序列_10

根据题意,我们可以枚举每个 【月度刷题计划同款】经典 LCS 问题_子序列_11,检查其是否为其他 【月度刷题计划同款】经典 LCS 问题_后端_12 的子序列,这需要枚举所有点对,复杂度为 【月度刷题计划同款】经典 LCS 问题_子序列_13。同时记录遍历过程中的最大长度 ans,用于剪枝(对于字符串长度本身小于等于 ans【月度刷题计划同款】经典 LCS 问题_后端_05

我们可以实现一个 check 函数来检查 s1 是否为 s2 的子序列,该问题可转化为求 s1s2 的最长公共子序列长度。若最长公共子序列长度为 s1 长度,说明 s1s2 的子序列,此时 【月度刷题计划同款】经典 LCS 问题_后端_05 不满足条件,否则我们使用 【月度刷题计划同款】经典 LCS 问题_后端_05 的长度来更新 anscheck 函数的复杂度为 【月度刷题计划同款】经典 LCS 问题_复杂度_17

不了解 LCS 的同学可以看前置

标签:LCS,strs,复杂度,序列,字符串,同款,长度,刷题
From: https://blog.51cto.com/acoier/6509109

相关文章

  • [刷题笔记] Luogu P1379 八数码
    ProblemSolution题意非常明确,显然搜索,搜索的时候存储八数码可以用二维或者一维,但是个人感觉用二维更明了一些。需要注意去重,去重可以用set维护一下已经搜过的八数码,如果手写去重小心MLE具体实现的时候注意一下细节。Code#include<iostream>#include<cstdio>#include<al......
  • 算法刷题记录:AcWing 4908. 饥饿的牛
    目录题目链接:题目分析:时间复杂度SF代码AC代码:题目链接:https://www.acwing.com/problem/content/description/4911/题目分析:数据范围最大\(10^{14}\),所以如果采用枚举一定会TLE,因为只有\(10^5\)天会运来新的草,所以我们可以只考虑运草的天。假设当前到\(d_2\)天之前剩余干......
  • [刷题笔记] CF1059B Forgery
    ProblemSolution搜索染色类。我们发现染色是不可逆的,也就是染成了#后不得染回“.”,所以对于每次染色我们都要尽可能向std上靠拢。我们可以观察一下std,发现需要尽可能从std上的“.”向四周染色(因为3*3染色中间的"."不染)。每次染色前需要判断染完这一部分是否和std一致,如果一......
  • 20230612刷题总结
    2023/06/12刷题总结A-DoubleCola如果n在1到5之间先单独判断是谁.如果大于5之后,用一个cnt记录当前这一组由几个人排在一起,然后使用循环每次动态的删除人数,直到找到n在那一组,然后将剩下的n直接整除pow(2,cnt)就可以了.#include<bits/stdc++.h>#defineintlonglong#d......
  • 同款爱心代码
    <!DOCTYPEhtml><html><head><metahttp-equiv="Content-Type"content="text/html;charset=UTF-8"><title>......
  • P1707 刷题比赛 题解
    多少有点混乱邪恶。题意:给出递推式:\[a_1=b_1=c_1=1\\a_2=b_2=c_2=3\\\begin{aligned}a_k&=p\timesa_{k-1}+q\timesa_{k-2}&+b_{k-1}+c_{k-1}&+r(k-2)^2+t(k-2)+1\\b_k&=u\timesb_{k-1}+v\timesb_{k-2}&+a_{k-1}+c_{k-1}&+w^{k-2}\\c......
  • java刷题网站最近更新的面试题
    49个人中至少几个人生日是同一月?如何用3升和5升桶量取4升水?JVM逃逸分析默认是开启还是关闭?ZGC有缺点吗?JVM对Java的原生锁做了哪些优化?为什么wait(),notify()和notifyAll()必须在同步方法或者同步块中被调用?什么是锁消除和锁粗化?为什么代码会重排序?什么是自旋?你们线程池是怎......
  • 算法刷题记录:P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two
    题目链接:https://www.luogu.com.cn/problem/P1518题目分析这道模拟题很典型了,给定了一个固定的移动方式,去模拟即可,该题说:如果牛和农夫永远不会相遇输出0,我没想到很好的方法,不推荐我这样的写法。算勉强AC吧。AC代码//Problem:P1518[USACO2.4]两只塔姆沃斯牛TheTamwort......
  • 算法刷题记录:P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布
    题目链接https://www.luogu.com.cn/problem/P1328题目分析是一道和环有关的问题,直接模拟即可AC代码//Problem:P1328[NOIP2014提高组]生活大爆炸版石头剪刀布//Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1328//MemoryLimit:125MB//TimeLimit......
  • 算法刷题记录:P4924 [1007]魔法少女小Scarlet
    题目链接https://www.luogu.com.cn/problem/P4924题目分析题意为将以[x,y]为中心某个矩阵,逆时针/顺时针旋转。所以其本质就是矩阵的旋转,所以找出通项公式即可。通项公式:顺时针:x后=x+y-y原,y后=y-x+x原逆时针:x后=x-y+y原,y后=x+y-x原AC代码//Problem:P4924[1007]魔法少......