9ms, C++, O(min(n,m)) Space, 10 lines


  • 0
    V

    Many entries are O(n+m) space, but a slight change helps to get O(min(n,m)) space. Additionally, the no-op doesn't need to be its own operation, but can be a special case of substitution.

    class Solution {
            public:
                    int minDistance(string word1, string word2) {
                            if (word2.size() > word1.size()) std::swap(word1, word2);
                            std::vector<int> dist_i_1(word2.size()), dist_i(word2.size());
                            std::iota(dist_i_1.begin(), dist_i_1.end(), 1);
                            for (int i = 0; i < word1.size(); i++, std::swap(dist_i_1, dist_i))
                                    for (int j = 0, dist_i_j_1 = i; j < word2.size(); j++)
                                            dist_i_j_1 = dist_i[j] = min({
                                                            dist_i_1[j] + 1,
                                                            (j-1 < 0 ? i : dist_i_1[j-1]) + (word1[i] == word2[j] ? 0 : 1),
                                                            dist_i_j_1 + 1});
                            return word2.size() > 0 ? dist_i_1.back() : word1.size() - word2.size();
                    }
    };
    

Log in to reply
 

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