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.

Solutions

  • Method 1: 2 pointers 
      class Solution {
      public boolean isSubsequence(String s, String t) {
          int sLen = s.length(), tLen = t.length();
          if(sLen > tLen) return false;
          else if(sLen == 0) return true;
          int index1 = 0, index2 = 0;
          while(index1 < sLen && index2 < tLen){
              if(s.charAt(index1) == t.charAt(index2)){
                  index1++;
                  index2++;
              }else{
                  index2++;
              }
          }
          return index1 == sLen;
      }
  }
  • Method 2: dp 
      class Solution {
      public boolean isSubsequence(String s, String t) {
          int sLen = s.length(), tLen = t.length();
          boolean[][] dp = new boolean[tLen + 1][sLen + 1];
          for(int i = 0; i <= tLen; i++){
              dp[i][0] = true;
          }
          for(int i = 1; i <= tLen; i++){
              for(int j = 1; j <= sLen; j++){
                  if(s.charAt(j - 1) == t.charAt(i - 1)){
                      dp[i][j] = dp[i - 1][j - 1];
                  }else{
                      dp[i][j] |= dp[i - 1][j];
                  }
              }
          }
          return dp[tLen][sLen];
      }
  }