How to come up with solution?
Hey there! Just a typical and pretty straight forward problem, but .... (do not worry! Probelm is actually easy and somewhat teaches you to take a look on compl
Hey there! Just a typical and pretty straight forward problem, but .... (do not worry! Probelm is actually easy and somewhat teaches you to take a look on complexities to analyze futher optimizations)\n___\n***Brute force*** [_Time Limit Exeeded_](https://leetcode.com/submissions/detail/752081090/)\nThis is there trobles come into play - the most obvious solution can\'t simply work out, cause of Leetcode\'s time limitation. If you see the last test case that didn\'t work out you\'ll see just a huge string on input and a lot of equal strings. But for now let\'s stick to the origin code:\n```\npublic int numMatchingSubseq(String s, String[] words) {\n        int count = 0;\n        for (int i = 0; i < words.length; i++) {\n            if (isSubsequence(s, words[i]))\n                count++;\n        }\n        return count;\n    }\n    \n    private boolean isSubsequence(String s, String word) {\n        int ptrS = 0;\n        int ptrW = 0;\n        while (ptrS < s.length() && ptrW < word.length()){\n            if (s.charAt(ptrS) == word.charAt(ptrW))\n                ptrW++;\n            ptrS++;\n        }\n        return ptrW == word.length();\n    }\n```\nTime complexity: O(k * max(m, n) - where n is a size of input string, m - size of max array element, k - size of iput array  (sorry for such naming, that\'s exactly what is wrote on the paper doing this problem ;{ )\nSpace complexity: O(1) \n\nAnd we got the full picture now - algorithm is pretty good, but fails to do this akward input. As you can see above, for this solution no additional space required, can we use some to benefit out total time?\n___\n***Optimazied no extra space*** [228ms 54.4MB](https://leetcode.com/submissions/detail/752115087/)\nWell, go back to faild test and see the following - input string had a great deal on overall complexity (since it dominates element size) and we got \n\nO ( inputString. length() * array.length )\n\nSo let\'s think of reducing one of the following pruducts. Since we absolutly need to traverse the whole array no matter what, only first element is left for us to optimized. Let\'s reduce the problem to the following:\ninput string: "a1a2a3......an"\ninput array: ["b1b2", .... "bn"]\nIn here, if the first element of an array is actually a subsequnce of input string, then **next element, being a subsequence of the first will be a subsequence of the input string, overwise check if this element is actually a subsequnce of the input string**. It will make much more sence in code:\n```\npublic int numMatchingSubseq(String s, String[] words) {\n        int count = 0;\n        Integer prevSub = null;\n        Integer prevNot = null;\n        for (int i = 0; i < words.length; i++) {\n            if (prevSub != null && isSubsequence(words[prevSub], words[i])) {\n                prevSub = words[i].length() > words[prevSub].length() ? i : prevSub;\n                count++;\n            } else if (prevNot != null && isSubsequence(words[prevNot], words[i])) {\n                continue;\n            } else if (isSubsequence(s, words[i])) {\n                prevSub = i;\n                count++;\n            } else {\n                prevNot = i;\n            }\n        }\n        return count;\n    }\n    \n    private boolean isSubsequence(String s, String word) {\n        int ptrS = 0;\n        int ptrW = 0;\n        while (ptrS < s.length() && ptrW < word.length()){\n            if (s.charAt(ptrS) == word.charAt(ptrW))\n                ptrW++;\n            ptrS++;\n        }\n        return ptrW == word.length();\n    }\n```\nThough time and space complexities are the same, that will pass because optimization with last subsequence element and last not subsequence take us a greate deal. But leetcode points out that there are a lot of other fellows done this problem somehow faster. Let\'s move on then!\n___\n***Optimizing with extra space*** [29ms 59.4MB](https://leetcode.com/submissions/detail/752149377/)\nSo this approach is to take advantage of particaular problem\'s detail that is consists only of lowercase English letters. We will have Linked list of words, where heads will contins first letter. And next we will only compare one of 26 lists (thier nodes actually) on being subsequence. Code is self-descibing:\n```\npublic int numMatchingSubseq(String s, String[] words) {\n        Word[] heads = new Word[26];\n        // fill the heads\n        for (int i = 0; i < 26; i++) heads[i] = new Word("", 0);\n        for (String word : words) {\n            Word head = heads[word.charAt(0) - \'a\'];\n            Word newWord = new Word(word, 0);\n            newWord.next = head.next;\n            head.next = newWord;\n        }\n        int count = 0;\n        for (char c : s.toCharArray()) {\n            Word curHead = heads[c - \'a\'];\n            Word cur = curHead.next;\n            curHead.next = null;\n            while (cur != null) {\n                Word next = cur.next;\n                if (cur.index == cur.word.length() - 1) {\n                    count++;\n                } else {\n                    cur.index++;\n                    Word nextHead = heads[cur.word.charAt(cur.index) - \'a\'];\n                    cur.next = nextHead.next;\n                    nextHead.next = cur;\n                }\n                cur = next;\n            }\n        }\n        return count;\n    }\n    \n    class Word {\n        String word;\n        int index;\n        Word next;\n        Word(String word, int index) {\n            this.word = word;\n            this.index = index;\n        }\n    }\n```\nTime complexity: O(n) since its one time pass\nSpace complexity: O(k * m) store an input array in the list
['Java']