C++ LCS DP, beats 99.27% with explanation


  • 0
    G

    The idea behind it is simple. If there are two strings then we have to take the max part that is equal between the two (this is LCS). Since this part is common between the two strings, we just subtract it from each of the two sizes.

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

Log in to reply
 

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