Question

One edit away

Check if two strings are one edit away

pale, ple -> true
pale, bake -> false

image-uploaded-from-ios-1

Can be solved by induction and optimized by dynamic programming


int HowManyEdits_recursion(const char* A, const char* B, int i, int j) {
    if (i < 0 || j < 0) return 0;

    if (A[i] == B[j]) {
        return HowManyEdits_recursion(A, B, i - 1, j - 1);
    }
    else {
        return MIN3(HowManyEdits_recursion(A, B, i, j - 1), HowManyEdits_recursion(A, B, i - 1, j), HowManyEdits_recursion(A, B, i - 1, j - 1)) + 1;
    }
}

class SUBSOL {
public:
    SUBSOL(int a_len, int b_len) {
        this->a_len = a_len;
        this->b_len = b_len;
        solutions = new int[a_len * b_len];
        memset(solutions, 0, sizeof(int) * a_len * b_len);

    }
    virtual ~SUBSOL() {
        delete[] solutions;
    }

    int getVal(int i, int j) {
        if (i < 0 || j < 0) return 0;
        return solutions[i * b_len + j];
    }
    void setVal(int i, int j, int val) {
        solutions[i * b_len + j] = val;
    }

private:
    int* solutions;
    int a_len;
    int b_len;
};
int HowManyEdits(const char* A, const char* B, int A_len, int B_len) {
    SUBSOL sub(A_len, B_len);

    for (int i = 0; i < A_len; i++) {
        for (int j = 0; j < B_len; j++) {
            if (A[i] == B[j]) {
                sub.setVal(i, j, sub.getVal(i - 1, j - 1));
            }
            else {
                sub.setVal(i, j, MIN3(sub.getVal(i, j - 1), sub.getVal(i - 1, j), sub.getVal(i - 1, j - 1)) + 1);
            }
        }
    }

    return sub.getVal(A_len - 1, B_len - 1);
}

int HowManyEdits(const char* A, const char* B) {
    bool recursion = false;
    if (recursion) {
        return HowManyEdits_recursion(A, B, strlen(A) - 1, strlen(B) - 1);
    }
    else {
        return HowManyEdits(A, B, strlen(A), strlen(B));
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s