给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
public boolean isSubsequence(String s, String t) { int m=s.length(),n=t.length(); //dp数组表示s中以i-1为结尾的字符串和t中以j-1为结尾的字符串的公共子序列的长度，若最右下角的数值等于m字符串的长度则说明为子序列 //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]; 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; }
贪心算法
我们初始化两个指针 ii 和 jj，分别指向 ss 和 tt 的初始位置。每次贪心地匹配，匹配成功则 ii 和 jj 同时右移，匹配 ss 的下一个位置，匹配失败则 jj 右移，ii 不变，尝试用 tt 的下一个字符匹配 ss。最终如果 ii 移动到 ss 的末尾，就说明 ss 是 tt 的子序列。
public boolean isSubsequence(String s, String t) { int n = s.length(), m = t.length(); int i = 0, j = 0; while (i < n && j < m) { if (s.charAt(i) == t.charAt(j)) { i++; } j++; } return i == n; }
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
public static int com(int[] nums){ //关键是遍历数组中的每个点，一每个点作为子序列的最后 结尾，然后二次循环从前往后寻找最大的子序列长度 int[] dp=new int[nums.length]; for(int i=0;i<dp.length;i++) dp[i]=1; for(int j=1;j<dp.length;j++){ int max=0; for(int i=0;i<j;i++){ if(nums[i]<nums[j]){ max=Math.max(max,dp[i]); } } dp[j]=dp[j]+max; } return Arrays.stream(dp).max().getAsInt(); }
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。
最长公共子序列和第一题求判断子序列类似
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
引用官方图片
class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; char c1 = s.charAt(i); for (int j = i + 1; j < n; j++) { char c2 = s.charAt(j); if (c1 == c2) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } }
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
public int minDistance(String word1, String word2) { int[][] dp=new int[word1.length()+1][word2.length()+1]; for(int i=1;i<dp.length;i++){ for(int j=1;j<dp[0].length;j++){ if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); } } int i = word2.length() + word1.length() - 2 * dp[word1.length()][word2.length()]; return i; }
