Recursion with Greedy
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about finding whether word2 can be matched as a subsequence of word1 wit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about finding whether `word2` can be matched as a subsequence of `word1` with at most one mismatch. The idea is to traverse both strings simultaneously, trying to match characters. If a character mismatch occurs, we have one chance to ignore this mismatch (using a flag). Memoization helps to avoid redundant computations by storing previously visited states.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use a recursive function with memoization (via a set) to avoid reprocessing the same state.\n2. The recursive function `start()` takes three parameters: current indices `i` (for `word1`) and `j` (for `word2`), and a `flag` that indicates whether a mismatch is still allowed.\n3. If characters at `i` and `j` match, move both indices forward. If they don\'t match, either skip a character in `word1` (if the flag allows) or continue searching for the next match.\n4. If the entire `word2` is matched, return true and store the indices in the solution vector. Reverse the vector at the end to get the correct order of indices.\n5. If no valid subsequence is found, return an empty vector.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity is approximately $$O(nmlogm)$$, where `m` is the length of `word1` and `n` is the length of `word2`. Each combination of `i` and `j` can be visited once with a possible flag state, making the maximum number of recursive calls.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is $$O(n*m)$$ due to the memoization set `s1` storing visited states. \n\n# Code\n```cpp\nclass Solution {\n    set<pair<int, pair<int, int>>> s1;\npublic:\n    bool start(int i, int j, int flag, string &word1, string &word2, vector<int> &sol) {\n        if (j >= word2.size()) return true;\n        if (i >= word1.size()) return false;\n        if (s1.count({i, {j, flag}})) return false;\n\n        bool f1 = false;\n\n        if (word1[i] == word2[j]) {\n            f1 = start(i + 1, j + 1, flag, word1, word2, sol);\n            if (f1) sol.push_back(i);\n            return f1;\n        } else {\n            if (flag > 0) {\n                f1 = start(i + 1, j + 1, 0, word1, word2, sol);\n                if (f1) {\n                    sol.push_back(i);\n                    return true;\n                }\n            }\n\n            while (i < word1.size() && word1[i] != word2[j]) i++;\n            if (i < word1.size()) {\n                f1 = start(i + 1, j + 1, flag, word1, word2, sol);\n                if (f1) {\n                    sol.push_back(i);\n                    return true;\n                }\n            }\n        }\n\n        s1.insert({i, {j, flag}});\n        return f1;\n    }\n\n    vector<int> validSequence(string word1, string word2) {\n        vector<int> sol;\n        if (start(0, 0, 1, word1, word2, sol)) {\n            reverse(sol.begin(), sol.end());\n            if (sol.size() == word2.size()) return sol;\n        }\n        return {};\n    }\n};\n```\n\n# Note :- `This Solution is not working now`\n
['Hash Table', 'C++']