[Space Efficient Sol] C++ Solution in O(n*m) time and O(n) space


#1

Refer to this for in-depth explanation.

int Solution::minDistance(string A, string B) {
    // A along cols, B along rows
    int rows = B.length(), cols = A.length();
    vector<int> prev(cols+1);
    for(int i=0; i<=cols; i++)
        prev[i] = i;
    
    for(int i=1; i<=rows; i++){
        vector<int> dp(cols+1);
        dp[0] = i;
        for(int j=1; j<=cols; j++){
            if(A[j-1]==B[i-1])
                dp[j] = prev[j-1];
            else
                dp[j] = min(min(prev[j], prev[j-1]), dp[j-1])+1;
        }
        swap(prev, dp);
    }
    return prev.back();
}