Levenshtein Distance

[alan0428a]

Back To Back SWE

The solution uses bottom-up DP approach to solving the question. The solution provided now uses Top-Down Memoized approach.

Your email registered on BackToBackSWE :

alan0428a@gmail.com

Category of the bug :

• [ ] Question
• [x] Solution
• [ ] Language

Code you used for Submit/Run operation :

class Solution {
  public:
    int levenshteinDistance(string s1, string s2)
{
    int len1 = s1.size();
    int len2 = s2.size();

    vector<vector<int>> dp (len2 + 1, vector<int>(len1 + 1, 0));

    // Initialize first row and column
    for(int j = 1; j < dp[0].size(); j++)
    {
        dp[0][j] = j;
    }

    for(int i = 1; i < dp.size(); i++)
    {
        dp[i][0] = i;
    }

    for(int i = 1; i < dp.size(); i++)
    {
        char target = s2[i - 1];
        for(int j = 1; j < dp[i].size(); j++)
        {
            char current = s1[j - 1];
            if(current == target)
            {
                // Ending characters are the same, doesn't contribute to distance.
                // The distance is as same as the sub problem result of both index - 1
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                // Ending characters are diffrent, check which operations has min value
                int insert = dp[i - 1][j];
                int remove = dp[i][j - 1];
                int replace = dp[i - 1][j - 1];

                int minOperation = min(min(insert, remove), replace) + 1;
                dp[i][j] = minOperation;
            }
        }
    }
    return dp.back().back();
}

};

Language used for code :

C++

[alan0428a]

Also I think the video provided can be replace with the one you have on Youtube. That one has better quality than the one on the platform.