随想录算法训练营第五十四天|392.判断子序列、115.不同的子序列

392.判断子序列

public class Solution {
    public bool IsSubsequence(string s, string t) {
        if(s.Length==0)
        {
            return true;
        }
        int k=0;
        for(int i=0;i<t.Length;i++)
        {
            if(s[k]==t[i])
            {
                k++;
                
            }
            if(k==s.Length)
            {
                return true;
            }
            
        }
        return false;
    }
}

采用双指针，一个指针指向S的第一个元素，另一个指向T的第一个元素，采用一个For循环，字符串T到末尾就结束循环。在循环中如果两个元素相同，S的指针就后移一位，如果K指针来到S的末尾就返回True，否则都是False。

115.不同的子序列

public class Solution {
    public int NumDistinct(string s, string t) {
        char[]s1=s.ToCharArray();
        char[]t1=t.ToCharArray();
        int[,] dp=new int[s1.Length+1,t1.Length+1];
        for(int i=0;i<s1.Length;i++)
        {
            dp[i,0]=1;
        }
        for(int j=1;j<t1.Length;j++)
        {
            dp[0,j]=0;
        }
        for(int i=1;i<=s1.Length;i++)
        {
            for(int j=1;j<=t1.Length;j++)
            {
                if(s1[i-1]==t1[j-1])
                {
                    dp[i,j]=dp[i-1,j-1]+dp[i-1,j];
                }else
                {
                    dp[i,j]=dp[i-1,j];
                }
            }
        }
        return dp[s1.Length,t1.Length];
    }
}

Dp[i,j]表示以I-1结尾的S串中有以J-1为尾的个数。如果两个元素相同，Dp[i,j]=Dp[i-1,j-1]+Dp[i-1,j]上一个状态加上S串除开最后一个元素之前的结果。