# LeetCode 329. Is Subsequence

<font color="#43a047">Easy</font>

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

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).

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.

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

額外條件：如果 `s` 為空字串則回視為 `true`，如果 `t` 為空字串則為 `false`

#### 解決方法 1
將 `s` 內的每個字元取出比對 `t` 中的字元，我們不用每個字元都重頭開始比對，如果有比對到相同的字元，則下個字元直接從上次的位置開始。
結束條件有：
1. `s` 比對到所有 `t` 的字元
2. `s` 尚留有字元未比對，但 `t` 已比對完所有字元

###### Java Code

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) {
            return true;
        }
        
        if (t.length() == 0) {
            return false;
        }
        
        int i = 0;
        int j = 0;
        char[] scs = s.toCharArray();
        char[] tcs = t.toCharArray();
        for (; i < scs.length; i++) {
            if (j >= tcs.length) {
                // s 尚留有字元未比對, 但 t 已比對完所有字元
                return false;
            }
            char sc = scs[i];
            for (; j < tcs.length; j++) {
                char tc = tcs[j];
                if (sc == tc) {
                    if (i == scs.length - 1) {
                        return true;
                    }
                    // break 的話, 必須自己 j++
                    j++;
                    break;
                }
            }
        }
        
        // 如果 s 最後 1 個字元比對完 t 剩下的字都沒有相同的就會執行到此
        return false;
    }
}