# LeetCode: Is Subsequence Solution

The author is not smart enough to come up with the DP solution in the first place

## 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var isSubsequence = function (s, t) {2  let indexOfS = 03  for (const char of t) {4    if (char === s[indexOfS]) {5      indexOfS++6    }7  }8
9  return indexOfS === s.length10}```

## 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.length22}```

## References

Original problem

LeetCode 1143 : Longest Common Subsequence

## Tags

leetcode

string

recursion

dynamic programming

## Next Post

LeetCode: Counting Bits

Aug 15, 2022

Convert to binary with toString() method

## Previous Post

LeetCode: Combination Sum

Aug 8, 2022

Recursively try all the possible cases

Search Posts