Javascript Memoization Solution;
Hello. So I went through a few solutions myself and ended up zeroing down on a memoization solution that for me is the most intuitive and was the easiest for me
Hello. So I went through a few solutions myself and ended up zeroing down on a memoization solution that for me is the most intuitive and was the easiest for me to understand.\n\nWhat we have to first realize is what is wrong with the brute force solution. To quickly lay it out, the brute force solution is\n1.) You loop through all the words in the ```words``` list then you determine if that word is a subsequence of ```string``` by looping through every character of word and comparing it to the original string.\n\nIf you really think about it, there\'s no way around this process. You have to check every single word, or else you might forget to count one, and there is no way to check if something is a valid substring without looping through each character and performing the necessary algorithm. \n\nHowever, there is one major improvement we can do on the bruteforce solution, and that is, once we know that one word is a valid or invalid subsequence, then all we have to do is remember its value, and instead of looping through the words for ```O(m) time complexity``` where m is the length of each word. We can do that operation in ```O(1) time``` by storing the value in a hashmap that maps each word to a boolean value.\n\nUsing that hashmap we are able to greatly improve our bruteforce solution by only having to check each instance of a word for subsequence validity once.\n\nHere is the code\n\n\n```\n/**\n * @param {string} s\n * @param {string[]} words\n * @return {number}\n */\nvar numMatchingSubseq = function(s, words) {\n    var result = 0;\n    var map = new Map();\n    for (let i = 0; i < words.length; i++){\n        if (words[i].length > s.length) continue;\n        if (isSubsequence(words[i], s, map)){\n            result++\n        }\n    }\n    return result\n};\n\nconst isSubsequence = (word, string, map) => {//you can use any method to determine the substring but I used indexOf()\n    if (map.has(word)) return map.get(word) //this one line of code helps the time complexity so much\n    let index = -1;\n    for (const c of word){\n\t\n\t/*what this loop does is that is uses the indexOf() function to check for a valid index of the\n\tcharacter in word. if the character in word doesn\'t exist in string it will return -1. We can also pass\n\tin a second parameter that gives the function a starting point so that it won\'t consider indexes\n\tthat we have already considered. No repeats*/\n        index = string.indexOf(c, index+1);\n        if (index == -1){\n            map.set(word, false);\n            return false;\n        }\n    }\n    map.set(word, true);\n    return true\n}\n```
['Memoization', 'JavaScript']