Take not take approach using memoization
\nTake, not take approach.\nmemoize for each posw2 the min index posw1 which is not building the result.\n\n# Code\ncpp []\nclass Solution {\n    unordered_map<
\nTake, not take approach.\nmemoize for each posw2 the min index posw1 which is not building the result.\n\n# Code\n```cpp []\nclass Solution {\n    unordered_map<int, vector<int>> presence;\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        vector<int> result;\n        dfs(word1, word2, result, 0, 0, 0);\n        return result;\n    }\n    bool dfs(string& w1, string& w2, vector<int>& result, int posw1, int posw2, int replace) {   \n        if (replace > 1) \n            return false;\n        if (posw2 >= w2.size()) {\n            return true;\n        }\n        if (posw1 >= w1.size()) \n            return false;\n        if (presence.find(posw2) != presence.end() && presence[posw2][replace] < posw1)\n            return false;\n        bool replaced = false;\n        if (replace < 1 && w1[posw1] != w2[posw2]) {\n            result.push_back(result.size() == 0 ? 0 : result.back() + 1);\n            replace = dfs(w1, w2, result, result.back() + 1, posw2 + 1, replace + 1);\n            if (replace)\n                return true;\n            else\n                result.pop_back();\n        }\n        int nextpos = -1;\n        for (int i = posw1; i < w1.size() && nextpos < 0; i++) {\n            if (w1[i] == w2[posw2]) {\n                nextpos = i;\n            }\n        }\n        if (nextpos == -1)\n            return false;\n        result.push_back(nextpos);\n        bool notreplace = dfs(w1, w2, result, nextpos + 1, posw2 + 1, replace);\n        if (notreplace) {\n            return true;\n        } else {\n            result.pop_back();\n            if (presence.find(posw2) == presence.end()) {\n                presence[posw2] = vector<int>(2, INT_MAX);\n            }\n            presence[posw2][replace] = min(presence[posw2][replace], posw1);\n            return false;\n        }\n    }\n   \n};\n```
['C++']