C++ Simple DP (Longest Common Subsequence)


  • 0
    F
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
            int max_val = 0;
            for (int i = 1; i <= word1.size(); ++ i)
                for (int j = 1; j <= word2.size(); ++ j)
                {
                    if (word1[i - 1] == word2[j - 1])
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    else
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 
                    max_val = max(max_val, dp[i][j]);
                }
            return word1.size() - max_val + word2.size() - max_val;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.