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

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

Comments

Loading comments...

Tags

leetcode

string

recursion

dynamic programming

Next Post

LeetCode: Counting Bits

Convert to binary with toString() method

Previous Post

LeetCode: Combination Sum

Recursively try all the possible cases

HoningJS

Search Posts