[Python3][1206 ms] Recursion and backtracking with caching
This is almost the solution I submitted during the contest, but there I was caching the whole word. Never cache the whole word when only the index will suffice!
This is almost the solution I submitted during the contest, but there I was caching the whole word. Never cache the whole word when only the index will suffice!\n\n\n# Approach\nLoop through the first word and add to the solution whenever you get a match with the second word, and then increment its current index (j). If you don\'t get a match, \n\n- Greedily skip one character from the second word, and see if you are getting a solution with no skips allowed. If you succeed, return the result. Else, continue the loop.\n\n# Note\n\nBecause we are always going forward, we only need to cache j, the current index of second word, and only during failures. This is because if index j failed previously in the iteration, when the value of i (index of the first word) was smaller, it is certain to fail now.\n\n# Code\n```python3 []\nclass Solution:\n    \n    def validSequence(self, W1: str, W2: str) -> List[int]:\n        cache = set()\n\n        N1 = len(W1)\n        N2 = len(W2)\n\n        def vS(i, j, subs = 1):\n            n1 = N1 - i\n            n2 = N2 - j\n        \n            if n1 < n2:\n                cache.add(j)\n                return []\n\n            if n1 == n2:\n                cache.add(j)\n                return list(range(i, N1)) if W1[i:] == W2[j:] else []\n        \n            j1 = j\n            ret = []\n        \n            for i1 in range(i, N1):\n                if j1 == N2:\n                    break\n                \n                if W1[i1] == W2[j1]:\n                    ret.append(i1)\n                    j1 += 1\n\n                elif subs:\n                    if j1 == N2 - 1:\n                        return ret + [i1]\n\n                    if j1 + 1 in cache:\n                        continue\n\n                    res = vS(i1 + 1, j1 + 1, subs = 0)\n                    if res:\n                        return ret + [i1] + res\n                        \n            cache.add(j)\n            return ret if len(ret) == n2 else []\n        return vS(0, 0)\n        \n        \n```
['Python3']