Python3 || dp  ||
Here\'s the plan:\n1. We populate the match_cnt, a list that tracks how many characters from word2 can be matched from each position of word1 as we traverse wor
Here\'s the plan:\n1. We populate the `match_cnt`, a list that tracks how many characters from `word2` can be matched from each position of `word1` as we traverse `word1` from right to left. We use `match_cnt` to track the potential number of matches starting from any given index in `word1`. If the current character in `word1` matches the current character in `word2`, the appropriate element of `match_cnt` is incremented.\n\n1. We construct the initial sequence of indices `ans`, in which characters from `word2` matched in `word1`. It iterates over `word1` , appending matching indices to `ans`. If the sequence length (`ans_len`) matches `word2`, we have an exact match, so the loop exits early. If not, we continue the iteration.\n2. If we do not have an exact match in 2) above, we attempt to complete it by substituting one character per the problem description.It starts from the next index after the last added match (or from the beginning if `ans` is empty). If we cannot find all but one remaining match, we return `[]`. Otherwise, it continues adding indices until the sequence fully matches word2. Finally, the completed sequence is returned.\n\n```python3 []\nclass Solution:\n    def validSequence(self, word1: str, word2: str) -> List[int]:\n        \n        n1, n2 = len(word1), len(word2)\n        w2_idx, ans_len = n2 - 1, 0\n        match_cnt, ans = [0] * (n1 + 1), []\n\n\n        for w1_idx in range(n1 - 1, -1, -1):            # <-- #1)\n\n            match_cnt[w1_idx] = match_cnt[w1_idx + 1]\n\n            if w2_idx == -1: continue\n\n            if word1[w1_idx] == word2[w2_idx]:\n                match_cnt[w1_idx]+= 1\n                w2_idx -= 1\n\n\n        for w1_idx in range(n1):                        # <-- #2)\n\n            if ans_len == n2: break\n\n            if word1[w1_idx] == word2[ans_len]: \n                ans.append(w1_idx)\n                ans_len+= 1\n            \n            elif match_cnt[w1_idx + 1] + ans_len >= n2 - 1:\n                ans.append(w1_idx)\n                ans_len+= 1\n                break\n    \n        if ans_len == n2: return ans\n\n        \n        w1_idx = 0 if not ans else ans[-1] + 1          # <-- #3)\n        w2_idx = ans_len\n\n        if match_cnt[w1_idx] + w2_idx < n2: return []\n\n        while w2_idx < n2:\n            if word1[w1_idx] == word2[w2_idx]:\n                ans.append(w1_idx)\n                w2_idx += 1\n            w1_idx += 1\n        \n        \n        return ans\n```\n\nI could be wrong, but I think that time complexity is *O*(*N2*) and space complexity is *O*(*N1*), in which *N1* ~ `len(words1)` and *N2* ~ `len(words2)`.
['Python3']