[C++] Solution


  • 1
    class Solution {
    public:
        int minDistance(string a, string b) {
            int m = a.size(), n = b.size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            dp[m][n] = 0;
            for (int i = m - 1; i >= 0; i--) {
                dp[i][n] = dp[i + 1][n] + 1;
            }
            for (int j = n - 1; j >= 0; j--) {
                dp[m][j] = dp[m][j + 1] + 1;
            }
    
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    int dela = 1 + dp[i + 1][j];
                    int delb = 1 + dp[i][j + 1];
                    int delab = (a[i] == b[j] ? 0 : 2) + dp[i + 1][j + 1];
                    dp[i][j] = std::min({dela, delb, delab});
                }
            }
            return dp[0][0];
        }
    };
    

  • 0

    WOW, I learn this function call

    template< class T >
    constexpr T min( std::initializer_list<T> ilist );
    

    from your code. Thanks


Log in to reply
 

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