How to use Recursion with Memoization In Javascript
- In this approach, we have defined the recursive function which finds the two possibilities at each step: whether the current characters in the string match or not.
- The memoization table is used to store the previously computed output results for the specific indices, and it ensures that there are no repeat calculations.
- Using this approach, we can traverse all possible combinations of characters and return the count of distinct occurrences of subsequences.
Example: In this example, we will count distinct occurrences as a subsequence using Recursion with Memoization approach
Javascript
function countSeq(str, seq) { const memoTable = new Map(); function helperFunction(strIdx, seqIdx) { if (seqIdx === seq.length) return 1; if (strIdx === str.length) return 0; const key = strIdx + ',' + seqIdx; if (memoTable.has(key)) return memoTable.get(key); let count = 0; if (str[strIdx] === seq[seqIdx]) { count += helperFunction(strIdx + 1, seqIdx + 1); } count += helperFunction(strIdx + 1, seqIdx); memoTable.set(key, count); return count; } return helperFunction(0, 0); } const str = "w3wiki" ; const seq = "ge" ; console.log(countSeq(str, seq)); |
6
Time complexity: O(2 ^ N), where ‘N’ is the length of the input.
Auxiliary space: O(2 ^ N), The space complexity is determined by the space used for the memoTable, which is a Map data structure. Stores for all unique combinations of strIndex and subseqIndex.
JavaScript Count Distinct Occurrences as a Subsequence
Counting the distinct occurrences is the most common problem in string manipulation. Subsequences are the subsets of the characters in the string which appear in the same order but not necessarily in a consecutive manner. In the problem, the task is to find out the count of how many times a given subsequence appears as a distinct occurrence in the given larger string. In this article, we will explore various approaches to count distinct occurrences as a subsequence
There are different approaches to counting distinct occurrences as a subsequence in JavaScript. Let’s discuss each one of them.
- Using Recursion with Memoization Approach
- Using String Iteration Approach
- Using BackTracking Approach