Given two strings, s and t, determine whether s is a subsequence of t. Return true if it is, otherwise return false.

A subsequence is a new string that can be obtained from the original by removing some (or none) of its characters while maintaining the order of the remaining characters. For example, "adef" is a subsequence of "abcdefg", but "afb" is not.

Example 1:

Input: s = "abc", t = "afbhdcg"
Output: true
Explanation: Keeping "a", "b", and "c" from t, while skipping "f", "h", "d", and "g", gives "abc" without changing the relative order of the kept characters.

Example 2:

Input: s = "abk", t = "ksbvay"
Output: false
Explanation: Although "a", "b", and "k" all appear in t, they do not appear in the order needed to form "abk".

Example 3:

Input: s = "eca", t = "hcia" 
Output: false
Explanation: The letter "e" is not present in t, so s cannot be formed as a subsequence.

Example 4:

Input: s = "", t = "abc"
Output: true
Explanation: The empty string is a subsequence of every string because no characters need to be matched.

Constraints

0 <= s.length <= 100

0 <= t.length <= 10⁴

s and t consist only of lowercase English letters.

30. Subsequence Check