LeetCode 392. 判断子序列 java题解

https://leetcode.cn/problems/is-subsequence/description/
转化为最长公共子序列问题。求[lens][j]的公共子序列长度是否为lens。

class Solution {
    //s属于t,lens<=lent
    public boolean isSubsequence(String s, String t) {
        int lens=s.length(),lent=t.length();
        if(s.length()==0) return true;
        if(lent<lens) return false;
        int[][] dp=new int[lens+1][lent+1];
        //[i][j]：前i个，[0,i-1]。求[lens][j]的公共子序列长度是否为lens
        //初始化：i为0或者j为0。公共子序列长度都为0
        //转化为最长公共子序列问题
        for(int i=1;i<=lens;i++){
            for(int j=1;j<=lent;j++){
                if(s.charAt(i-1)==t.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]);
                }
                if(i==lens&&dp[i][j]==lens){
                    return true;
                }
            }
        }
        return false;
    }
}

这道题应该算是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。
if (s[i - 1] == t[j - 1])
t中找到了一个字符在s中也出现了
if (s[i - 1] != t[j - 1])
相当于t要删除元素，继续匹配

本题 如果删元素一定是字符串t，而 1143.最长公共子序列 是两个字符串都可以删元素。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int len1=s.length();
        int len2=t.length();
        int i=0,j=0;
        int count=0;//=len1
        while(i<len1&&j<len2){
            char c1=s.charAt(i);
            char c2=t.charAt(j);
            /*while(c1=c2&&i<len1&&j<len2){
                count++;

            }*/
            if(c1==c2){
                count++;
                i++;
                j++;
            }
            else{
                j++;
            }
        }
        return count==len1?true:false;
    }
}