LeetCode: Is Subsequence Solution

Approach: straight-forward iteration

Iterate through

characters, check if each of character in is in

The result is true when the iterator (as index) of

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

and

Check if that length equals to

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