392. Is Subsequence

QUESTION:

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Example 1: s = “abc”, t = “ahbgdc”

Return true.

Example 2: s = “axc”, t = “ahbgdc”

Return false.

Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits: Special thanks to @pbrother for adding this problem and creating all test cases.

EXPLANATION:

我看了一下related topic：binary search，动态规划，还有贪心。其实我看完题目第一个想到的是动态规划，所以就采用了动态规划的方式来进行。
逻辑：

  1. 首先我们确定两个指针，一个a用来表示在s中的位置，一个b是t中的位置，确定结束的条件是t查找结束，或者已经找到全部s
  2. 然后我们再进行查找：首先需要找到s[a]的字符，在t[b]中，while循环直到找到或者到了t的末尾
  3. 如果能够找到就进行下一个循环，将a和b都+1进行递归

    SOLUTION:

    class Solution {
 public boolean isSubsequenceResult = false;
 public boolean isSubsequence(String s, String t) {
     isSubsequenceHelper(s,t,0,0);
     return isSubsequenceResult;
 }
    
 public void isSubsequenceHelper(String s,String t,int anchor ,int target){
     if(isSubsequenceResult) return;
     if(target==s.length()){
         isSubsequenceResult = true;
         return;
     }
     if(anchor<t.length()){
         while (anchor <t.length() && t.charAt(anchor)!=s.charAt(target)) anchor++;
         if(anchor==t.length()) return;
         else
             isSubsequenceHelper(s,t,anchor+1,target+1);
     }
 }
}
--> return <--