Python O(n) solution 100% in runtime and space complexity
Intuition\n Describe your first thoughts on how to solve this problem. \nRecursive approach with greedy\n\n# Approach\n Describe your approach to solving the pr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nRecursive approach with greedy\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCreate a map to store possible size of the word1 needed given random word2 size.\nThen iterate over the word1 and try to change the char that you are at for the matchable character for word2. Then check if this leads to a solution. If it does, hell yes, u got the min. If not, keep on iterating.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```python3 []\nclass Solution:\n    def validSequence(self, w: str, p: str) -> List[int]:\n        m = {}\n        j = len(p)-1\n        for i in range(len(w)-1, -1, -1):\n            if j == -1:\n                break\n            if w[i] == p[j]:\n                m[len(p)-j] = len(w)-i\n                j -= 1\n        def check(w, p):\n            if len(p) in m:\n                return m[len(p)] <= len(w)\n            return len(p) == 0\n        j = 0\n        res = []\n        for i in range(len(w)):\n            if j == len(p):\n                break\n            if p[j] == w[i]:\n                res.append(i)\n                j += 1\n            elif check(w[i+1:], p[j+1:]):\n                res.append(i)\n                l = []\n                xj = j+1\n                for xi in range(i+1, len(w)):\n                    if xj == len(p):\n                        break\n                    if w[xi] == p[xj]:\n                        xj += 1\n                        l.append(xi)\n                res.extend(l)\n                return res\n        if len(res) == len(p):\n            return res\n        return []\n```
['Python3']