Edit Distance C++ 100%


  • 0
    S
    class Solution {
    public:
        int minDistance(string a, string b) {
            int m = a.length(), n = b.length();
            int save[m+1][2];
            for(int i = 0; i <= n; i++)
            {
                for(int j = 0; j <= m; j++)
                {
                    if(i == 0)
                        save[j][i&1] = j;
                    else if(j == 0)
                        save[j][i&1] = i;
                    else
                    {
                        if(a[j-1] == b[i-1])
                            save[j][i&1] = save[j-1][(i+1)&1];
                        else
                            save[j][i&1] = min(save[j-1][i&1], min(save[j-1][(i+1)&1], save[j][(i+1)&1])) + 1;    
                    }
                }
            }
            return save[m][n&1];
            
        }
    };
    

Log in to reply
 

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