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.

    Runtime: 120 ms, faster than 12.75% of C++ online submissions for Is Subsequence.
    Memory Usage: 14.8 MB, less than 100.00% of C++ online submissions for Is Subsequence.

    1. class Solution {
    2. public:
    3. bool isSubsequence(string s, string t) {
    4. if (s.length() > t.length()) {
    5. return false;
    6. }
    7. if (s.empty() || t.empty()) {
    8. return true;
    9. }
    10. int pos = 0;
    11. for (int i = 0; i < t.length(); i++) {
    12. if (s[pos] == t[i]) {
    13. pos++;
    14. }
    15. if (pos == s.length()) {
    16. return true;
    17. }
    18. }
    19. return false;
    20. }
    21. };