K edit distance, C++ (gcc)

K edit distance

/* 23 K Edit Distance
Find all words from a dictionary that are k edit distance away.
*/
#include <vector>
#include <iostream>
using namespace std;

class Solution{
public: 
    vector<string> findAll(vector<string>& words, string target, int k) {
        vector<string> res;
        for(auto w: words){
            if(findDistance(w, target) == k)
                res.push_back(w);
        }
        return res;
    }
private:
    int findDistance(string s1, string s2){
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> D(m+1, vector<int>(n+1,0)); // D[i][j] distance between s1(i), s2(j)  
        
        // first row, m=0, n=0,1,2...
        for(int i=0; i<=n; i++) D[0][i] = i; // inserting 
        
        // first column, n=0, m=0,1,2...
        for(int i=0; i<=m; i++) D[i][0] = i; // deleting 
        
        // i,j = (1,1) + (x,y) 
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) { // i,j <= (i-1, j-1), (i-1,j), (i,j-1) 
                if(s1[i-1] == s2[j-1]) // NOTE：idx is i-1, not i
                    D[i][j] = D[i-1][j-1]; 
                else{
                    int a = D[i-1][j-1] + 1;
                    int b = D[i][j-1] + 1;
                    int c = D[i-1][j] + 1;
                    D[i][j] = min(a,min(b,c)); 
                }
            }
        }
        return D[m][n];
    }
};

int main() {
    vector<string> words = {"abc", "Abc", "aBc", "bc"};
    string target = "abc"; 
    int dist = 1; 
    Solution s; 
    vector<string> res = s.findAll(words, target, dist); 
    for(auto x: res)
        cout << x << " " ; 
    cout << endl;
    return 0; 
}


run \| edit \| history \| help	0