Copy of lee215 solution
Intuition\nI read Lee\'s solution and it was very nice... after I got to understand it! Definitely go support him, but I will explain it in my own words here.\n
# Intuition\nI read Lee\'s solution and it was very nice... after I got to understand it! Definitely go support him, but I will explain it in my own words here.\n\nThe first idea is: for every character in word2, if it matches with characters of word1 store the character with the largest index. This is because we want to return a **$$sequence$$** of indices, which can only be increasing. If for every character in word2 that matches characters in word1 we get the one that is closest to the end of word1 as possible, we can find a character to change in word1 easier without worrying that if we changed it, another character that is needed in somewhere further back in the array will be unmatched.\nTo do this, Lee used a `last` array and went through word1 in a reverse order. The code should be pretty clear.\n\nOnce we have done that, we can go on to find the result. We create a pointer to an character of word2, starting from the first one. Iterating through each character of word1, we check if the character of word1 matches the character of word2 at index j. If they match, we can increase j. If they don\'t match and we haven\'t performed a swap before, we check if the index of `last` of the next character in word2 is greater than i, because if it is not, it means that it will be impossible to match that next character. If `skip` is greater than zero, that means that we have already swapped a character for word1, and therefore we cannot enter the if statement. Lastly, if j == m - 1, it means that we are at the last character of word2 (no more characters after that), so we can just check if we swapped before.\n\n# Code\n```python3\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        n, m = len(word1), len(word2)\n        last = [-1] * m\n        j = m - 1\n        for i in range(n - 1, -1, -1):\n            if j >= 0 and word1[i] == word2[j]:\n                last[j] = i\n                j -= 1\n        res = []\n        skip = j = 0\n        for i, c in enumerate(word1):\n            if j == m: \n                break\n            if word1[i] == word2[j] or skip == 0 and (j == m - 1 or i < last[j + 1]):\n                skip += word1[i] != word2[j]\n                res.append(i)\n                j += 1\n        return res if j == m else []\n```
['Python3']