LeetCode: Is Subsequence Solution

Approach: straight-forward iteration

Iterate through t characters, check if each of character in s is in t

The result is true when the iterator (as index) of s equals to its length

Implementation

1var isSubsequence = function (s, t) {
2  let indexOfS = 0
3  for (const char of t) {
4    if (char === s[indexOfS]) {
5      indexOfS++
6    }
7  }
8
9  return indexOfS === s.length
10}

Approach: longest common subsequence (LCS)

This solution is just for reference or fun reading, the author suggests the reader to skip if you do not want to make your day harder...

Find the length longest common subsequence of s and t

Check if that length equals to s length

Implementation

1const lcs = function (text1, text2) {
2  const memo = Array.from({ length: text1.length + 1 }, _ =>
3    Array(text2.length + 1).fill(null)
4  )
5
6  const recursion = (m, n) => {
7    if (memo[m][n] !== null) return memo[m][n]
8
9    if (m === 0 || n === 0) return (memo[m][n] = 0)
10
11    if (text1[m - 1] === text2[n - 1])
12      return (memo[m][n] = 1 + recursion(m - 1, n - 1))
13
14    return (memo[m][n] = Math.max(recursion(m, n - 1), recursion(m - 1, n)))
15  }
16
17  return recursion(text1.length, text2.length)
18}
19
20var isSubsequence = function (s, t) {
21  return lcs(s, t) === s.length
22}

References

Original problem

LeetCode 1143 : Longest Common Subsequence