DP Ques || Medium to Hard DP || ✅🚩
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(n*m*logn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    set<pair<int,pair<int,int>>>st;\n    bool solve(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(st.count({i,{j,flag}}))return false;\n\n        bool f1=false;\n        if(word1[i]==word2[j]){\n            f1 = solve(i+1,j+1,flag,word1,word2,sol);\n            if(f1){\n                sol.push_back(i);\n                return true;\n            }\n        }\n        else{\n            if(flag>0){\n                f1 = solve(i+1,j+1,0,word1, word2,sol);\n                if(f1){\n                    sol.push_back(i);\n                    return true;\n                }\n            }\n            while(i<word1.size() && word1[i]!=word2[j])i++;\n            if(i<word1.size()){\n                f1=solve(i+1,j+1,flag,word1,word2,sol);\n                if(f1){\n                    sol.push_back(i);\n                    return true;\n                }\n            }\n        }\n        st.insert({i,{j, flag}});\n        return f1;\n    }\n    vector<int> validSequence(string word1, string word2) {\n        vector<int> sol;\n        if(solve(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```
['Dynamic Programming', 'C++']