首页 > 其他分享 >392. 判断子序列(leetcode)

392. 判断子序列(leetcode)

时间:2024-09-08 14:15:42浏览次数:8  
标签:String int char 392 序列 leetcode

https://leetcode.cn/problems/is-subsequence/description/

class Solution {
    public boolean isSubsequence(String s, String t) {
        // 依据题意,可以判断是求最长公共子序列的特殊情况
        // f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1)
        // f[1][1]=1;
        int[][] f=new int[110][10010];
        char[] s1=s.toCharArray();
        char[] s2=t.toCharArray();
        for(int i=1;i<=s1.length;i++)
        {
            for(int j=1;j<=s2.length;j++)
            {
                f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
                if(s1[i-1]==s2[j-1])f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
            }
        }
        return f[s1.length][s2.length] == s.length();
        
    }
}

 

标签:String,int,char,392,序列,leetcode
From: https://www.cnblogs.com/lxl-233/p/18402821

相关文章

  • 时间序列结构变化分析:Python实现时间序列变化点检测
    平稳性是时间序列分析与预测的核心概念。在平稳条件下,时间序列的统计特性(如均值)在时间维度上保持不变,仅存在随机波动。但是实际数据集中很少观察到完全的平稳性。时间序列通常会经历结构性断裂或变化。这些变化会引入非平稳性,从而改变时间序列的整体分布,这些标志着变化开始的时间......
  • LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现N*K时间复杂度
    3177.求出最长好子序列II题目链接题目描述给你一个整数数组nums和一个非负整数k。如果一个整数序列seq满足在下标范围[0,seq.length-2]中最多只有k个下标i满足seq[i]!=seq[i+1],那么我们称这个整数序列为好序列。请你返回nums中好子序列的最长长度......
  • Leetcode 第 409 场周赛题解
    Leetcode第409场周赛题解Leetcode第409场周赛题解题目1:3242.设计相邻元素求和服务思路代码复杂度分析题目2:3243.新增道路查询后的最短距离I思路代码复杂度分析题目3:3244.新增道路查询后的最短距离II思路代码复杂度分析题目4:3245.交替组III思路代码复杂度......
  • LCP 485. 最大连续 1 的个数[lleetcode -11]
    从今天起,我们的算法开始研究搜索,首先就是DFS深度优先搜索(depth-firstseach,DFS)在搜索到一个新的节点时,立即对该新节点进行遍历;因此遍历需要用先入后出的栈来实现,也可以通过与栈等价的递归来实现。对于树结构而言,由于总是对新节点调用遍历,因此看起来是向着“深”的方向前进......
  • Leetcode 029 两数相除
    给你两个整数,被除数dividend和除数divisor。将两数相除,要求不使用乘法、除法和取余运算。整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345将被截断为8,-2.7335将被截断至-2。返回被除数dividend除以除数divisor得到的商。注意:假设我们的环境只能......
  • 【Golang】LeetCode面试经典150题:45. 跳跃游戏 II
    题干:给定一个长度为 n 的 0索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i+j] 处:0<=j<=nums[i] i+j<n返回到达 nums[n-1] 的最小跳跃次数......
  • Java反序列化漏洞-TemplatesImpl利用链分析
    目录一、前言二、正文1.寻找利用链2.构造POC2.1生成字节码2.2加载字节码1)getTransletInstance2)defineTransletClasses2.3创建实例3.完整POC三、参考文章一、前言java.lang.ClassLoader#defineClassdefineClass可以加载字节码,但由于defineClass的作用域是protected,所以攻......
  • 【SpringBoot实用小知识】JSON序列化返回结果时出现的幽灵成员
    幽灵成员问题的解决前言debug过程结论及解决方式1.更改方法名称2.为方法加上@JsonIgnore注解前言这是一个很令人无语的问题在最近写代码时发现一个问题就是有时候在测试接口的时候发现返回结果中出现了一些本不该出现的字段甚至有时候还报错信息如下Writing......
  • 代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II
    代码随想录刷题day25丨491.递增子序列,46.全排列,47.全排列II1.题目1.1递增子序列题目链接:491.非递减子序列-力扣(LeetCode)视频讲解:回溯算法精讲,树层去重与树枝去重|LeetCode:491.递增子序列_哔哩哔哩_bilibili文档讲解:https://programmercarl.com/0491.%E9%80......
  • LeetCode刷题 堆
    一:堆1、一种二叉树的结构(完全二叉树)2、完全二叉树:从上到下;从左到右;填满3、最大堆:根节点的权值大于孩子节点4、最小堆:根节点的权值依次小于孩子节点5、常用操作#创建堆(最大堆,最小堆)#添加元素#获取堆顶元素#删除堆顶元素#堆的长度#堆的遍历二:刷题215数组中的第K个最......