22.09.2023
392. Is Subsequence easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/347
Problem TLDR
Is the string a subsequence of another
Intuition
One possible way is to build a Trie, however this problem can be solved just with two pointers.
Approach
Iterate over one string and adjust pointer of another.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun isSubsequence(s: String, t: String): Boolean {
var i = -1
return !s.any { c ->
i++
while (i < t.length && t[i] != c) i++
i == t.length
}
}