Beats 100%||Bottom Up Approach||Using 2D DP|| Iterative Approach
\n\n# Approach\nusing base case initialize the values of dp array outside the len1 and len2\n\n# Complexity\n- Time complexity:\nO(len1len2)\n\n- Space complexi
\n\n# Approach\nusing base case initialize the values of dp array outside the len1 and len2\n\n# Complexity\n- Time complexity:\nO(len1*len2)\n\n- Space complexity:\nO(len1+1*len2+1)\n\n# Code\n```\nclass Solution {\npublic:\n//bottom up approach\n    int minDistance(string word1, string word2) {\n        int len1=word1.length();\n        int len2=word2.length();\n        vector<vector<int>>dp(len1+1,vector<int>(len2+1,-1));\n        for(int j=0;j<=len2;j++){\n            dp[len1][j]=len2-j;\n        }\n        for(int i=0;i<=len1;i++){\n            dp[i][len2]=len1-i;\n        }\n        for(int i=len1-1;i>=0;i--){\n            for(int j=len2-1;j>=0;j--){\n                    int ans;\n                if(word1[i]==word2[j]){\n                    ans=dp[i+1][j+1];\n                }else{\n                //if not matches then three operations\n                int insert=1+dp[i][j+1];\n                int delet=1+dp[i+1][j];\n                int replace=1+dp[i+1][j+1];\n                ans=min(insert,min(delet,replace));\n                }\n            dp[i][j]=ans; \n            }\n        }\n        return dp[0][0];\n    }\n};\n```
['String', 'Dynamic Programming', 'String Matching', 'C++']