class Solution {public:    int minDistance(string word1, string word2) {        int l1 = word1.length();        int l2 = word2.length();        vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));        for (int i = 1; i <= l1; i++) {            dp[i][0] = i;        }        for (int i = 1; i <= l2; i++) {            dp[0][i] = i;        }        for (int i = 1; i <= l1; i++) {            for (int j = 1; j <= l2; j++) {                if (word1[i - 1] == word2[j - 1]) {                    dp[i][j] = dp[i - 1][j - 1];                } else {                    dp[i][j] = min(dp[i - 1][j - 1],                            min(dp[i - 1][j], dp[i][j - 1])) + 1;                }            }        }        return dp[l1][l2];    }};class Solution2 {public:    int minDistance(string word1, string word2) {        int l1 = word1.length();        int l2 = word2.length();        int dp[l2 + 1] { 0 };        for (int i = 1; i <= l2; i++) {            dp[i] = i;        }        for (int i = 1; i <= l1; i++) {            int pre = i;            for (int j = 1; j <= l2; j++) {                int cur;                if(word1[i-1] == word2[j-1]){                    cur = dp[j-1];                }else{                    cur = min(dp[j-1],min(dp[j],pre))+1;                }                dp[j-1] = pre;                pre = cur;            }            dp[l2] = pre;        }        return dp[l2];    }};