Share my 10-lines c++ solution with O(n) space


  • 0
    H
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int sz2=word2.size();
            vector<int> step(sz2+1);
            for(int i=0;i<=sz2;i++)
                step[i]=sz2-i;
            for(int i1=word1.size()-1;i1>=0;i1--) {
                for(int i2=sz2-1,last=step[sz2]++;i2>=0;i2--) {
                    last=min(last+(word1[i1]!=word2[i2]),min(step[i2],step[i2+1])+1);
                    swap(last,step[i2]);
                }
            }
            return step[0];
        }
    };
    

Log in to reply
 

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