leetcode 392.判断子序列（Java 贪心）

╰半夏微凉° 2023-08-17 17:01 111阅读 0赞

[https://leetcode-cn.com/problems/is-subsequence/submissions/][https_leetcode-cn.com_problems_is-subsequence_submissions]

给定s和t序列，判断s是否是t的子序列。

1.贪心，两个指针a和i，分别遍历s和t，遇到一样的就a++，不管怎么样，i一直++。如果a和s.length()相等，return true。

class Solution {
        public boolean isSubsequence(String s, String t) {
            if(s.length()==0) return true;
            int tLen=t.length();
            int a=0;
            for(int i=0;i<tLen;i++){
                if(s.charAt(a)==t.charAt(i)){
                    a++;
                }
                if(a==s.length())                 //此语句要放在循环内部
                    return true;
            }
            return false;
        }
    }

2.动态规划

dp\[i\]\[j\]代表s序列从头到i是否是t序列从头到j的子序列。

则顺序遍历s、t序列，需要判断两种情况：

（1）s\[i\]==t\[j\]：则dp\[i\]\[j\]=dp\[i-1\]\[j-1\]

（2）s\[i\]!=t\[j\]：则dp\[i\]\[j\]=dp\[i\]\[j-1\]class Solution \{ *    public boolean isSubsequence(String s, String t) \{*

int sLen=s.length(),tLen=t.length();
            if(sLen>tLen) return false;
            if(sLen==0) return true;
            boolean[][] dp=new boolean[sLen+1][tLen+1];
            for(int j=0;j<=tLen;j++){                    //初始化，当s.length()=0时，dp[0][j]都为true。
                dp[0][j]=true;
            }
            for(int i=1;i<=sLen;i++){
                for(int j=1;j<=tLen;j++){
                    if(s.charAt(i-1)==t.charAt(j-1))      //dp[0][0]表示s和t序列长度为0，即没有字符，所
    　　　　　　　　　　　　dp[i][j]=dp[i-1][j-1];            //以dp要比s和t多一个，即dp[1][1]表示的是
                    else                                  //s[0]和t[0]
                        dp[i][j]=dp[i][j-1];
                }
            }
            return dp[sLen][tLen];
        }
    }

转载于:https://www.cnblogs.com/y1040511302/p/11528328.html

[https_leetcode-cn.com_problems_is-subsequence_submissions]: https://leetcode-cn.com/problems/is-subsequence/submissions/