This blog was last modified 515 days before.

Question Description

In this question, we are given 2 different strings, let's call it source and target. We are allowed to perform following operations for any times to source string:

• Insert a new character (E.g.: abc -> abxc)
• Delete a character (E.g.: abc -> ac)
• Change a character (E.g.: abc -> anc)

Now ask, what's the minimum steps we need to perform on source to make source == target.

E.g.:

When source: abcdmabcd; target: abcdabcd. We only need to delete m in source, so the number of step we take is 1. When source: abc; target: abcabc. We need to add a, b, c respectively at the end, so the number of steps we take are 3.

For convenience, we use:

• $D(a,b)$ to denote the distance between two string $a$ and $b$.
• $L(a)$ to denote the length (number of characters) of string $a$.
• $a[l:r]$ to denote a sub-string of string $a$ with 1-indexed subscript. (E.g.: $a="abcd", a[1:3]="abc"$. Also we use negative numbers to represent the index that start counting from the end, e.g.: $a="abcd", a[1:-2]="abc"$, also we could say $a=a[1:-1]$)

It could be proved that for any string $a$ and $b$, we have: $D(a,b) = D(b,a)$.

Analysis

For this question, if we try to use brute force to solve, the time complexity would be extremely high when scale of the question (length of source and target) becomes larger. Here, we are going to solve this question by dynamic programming.

Basic Cases

Consider when source or target is empty. The only thing we could do to make this two equal is to adding or removing numbers. So in this case, $D(a,b) = L(a) + L(b)$

General Cases

Now consider any source and target string. There are three possible ways for us to get $D(a,b)$.

Define that:

Also, define an array dpArr[i][j], that dpArr[i][j] is equal to $D(a[1:i], b[1:j])$, in words, is the shortest steps to turn first i characters in source string source into the first j characters in target string target.

Now we can start to discuss the state transfer in this question. For any subproblem a->b:

Transfer 1

If we use $a[1:-2]$ to construct $b$, and delete the last character in $a$, then we get:

The first part $D(a[1:-2],b)$ is the shortest distance between $a[1:-2]$ and $b$, and the $1$ is because we need one more step to delete the last character in a: $a[-1]$

Transfer 2

If we use $a$, that is, the whole string $a[1:-1]$, to construct $b$, then there are two possible situations:

• When $not(a[-1], b[-1]) = 1$

This means the last character in these two strings a and b is not equal, then we would have:

The first part $D(a[1:-2],b[1:-2])$ is the shortest distance between $a[1:-2]$ and $b[1:-2]$, and the $1$ is because we need one more step to change the last character in a $a[-1]$ to make $a[-1] = b[-1]$.

• When $not(a[-1], b[-1]) = 0$

With the similar process, we get:

This time we don't need to change $a[-1]$ since $not(a[-1], b[-1]) = 0$, they are already equivalent.

In conclusion, we can represents this transfer by using the formula below:

Transfer 3

If we use $a[1:-1]$ to construct $b[1:-2]$, then use add character operation to add the last character, then we get:

So above all we have 3 state transfer formula, and since we want to minimize the steps we used, so the unified state transfer formula would be:

Code Implementation

Based on the conclusion, all we need to do now is to start iterate from the basic scale, find the optimal state transfer method among this three till we reach dpArr[source.length()][target.length()]

Here is a code implementation in C++17

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <fstream>
#include <ostream>

using std::cin, std::cout, std::endl;
using std::string, std::vector, std::fstream, std::ostream;
using std::ios;
using std::max, std::min;
using LL = long long;

const string rootFilePath = R"(C:\Programming\c++\AlgorithmDesign\4)";
const char endq = '\n';

LL dpArr[1000][1000] = {0};

// Data strcuture for every single question
struct CaseData {
    string source;
    string target;
    // The distances of this two string
    // When -1, represents that this question is unsolved
    LL distance = -1;

    // Constructor
    // Here we promise that the length of source is always
    // greater than length of target
    CaseData(string src, string tar) :
            source(src),
            target(tar) {
        if (src.length() < tar.length()) {
            source = tar;
            target = src;
        }
    }

    // If this cases has been solved
    bool isSolved() const {
        return (distance != -1);
    }

    friend ostream &operator<<(ostream &os, const CaseData &caseData);
};

// Overload cout operator for CaseData
ostream &operator<<(ostream &os, const CaseData &caseData) {
    os << "<CaseData: "
       << "source: " << caseData.source
       << " target: " << caseData.target
       << " distance: " << caseData.distance
       << ">";
    return os;
}


vector<CaseData> readTestCasesFromFile() {
    // create file object and open input file
    fstream inputFile;

    inputFile.open(rootFilePath + "/in.txt", std::ios::in);
    if (!inputFile.is_open()) {
        cout << "Can not open file: in.txt" << endq;
        exit(-1);
    }

    int casesCount;
    vector<CaseData> cases;
    string src, tar;
    inputFile >> casesCount;

    // read all cases based on the casesCount
    for (int i = 0; i < casesCount; ++i) {
        inputFile >> src >> tar;
        cases.emplace_back(src, tar);
    }

    inputFile.close();
    return cases;
}

// Solve this case, and directly write solution into case data ref
// Based on the dpArr size limit, length of src and tar could not exceed 1000
void solveCase(CaseData &caseData) {
    // if two are equivalent
    if (caseData.source == caseData.target) {
        caseData.distance = 0;
    }

    // get length
    int sourceLength = caseData.source.length();
    int targetLength = caseData.target.length();

    // variable for later ref
    int lastAlphabetNotEqual = 0;
    LL valueWhenUseLast, valueWhenNotUseLast, valueWhenAddLast;
    // start dynamic program process
    for (int targetCur = 0; targetCur <= targetLength; ++targetCur) {
        for (int sourceCur = 0; sourceCur <= sourceLength; ++sourceCur) {

            // when one of the cursor is equal to 0
            if (targetCur == 0 || sourceCur == 0) {
                dpArr[sourceCur][targetCur] = targetCur + sourceCur;
                continue;
            }
            // check last alphabet
            lastAlphabetNotEqual = 1;
            if (caseData.source[sourceCur - 1] == caseData.target[targetCur - 1]) {
                lastAlphabetNotEqual = 0;
            };
            // dpArr value candidate
            valueWhenUseLast = dpArr[sourceCur - 1][targetCur - 1] + lastAlphabetNotEqual;
            valueWhenNotUseLast = dpArr[sourceCur - 1][targetCur] + 1;
            valueWhenAddLast = dpArr[sourceCur][targetCur - 1] + 1;
            // update dpArr
            dpArr[sourceCur][targetCur] = min({valueWhenUseLast, valueWhenNotUseLast, valueWhenAddLast});
        }
    }
    caseData.distance = dpArr[sourceLength][targetLength];
}

void showDpTable(int sourceLength, int targetLength) {
    for (int i = 0; i <= sourceLength; ++i) {
        for (int j = 0; j <= targetLength; ++j) {
            cout << dpArr[i][j] << " ";
        }
        cout << endq;
    }
}

// Main function
int main() {
    vector<CaseData> cases = readTestCasesFromFile();
    fstream outputFile;
    outputFile.open(rootFilePath + "/out.txt", std::ios::out);
    for (auto &singleCase: cases) {
        solveCase(singleCase);
        cout << singleCase << endq;
        cout << "Following DP Arr" << endq;
        showDpTable(singleCase.source.length(), singleCase.target.length());
        outputFile << singleCase.distance << endq;
    }
    return 0;
}

In which, the most important state transfer part is:

for (int targetCur = 0; targetCur <= targetLength; ++targetCur) {
    for (int sourceCur = 0; sourceCur <= sourceLength; ++sourceCur) {

        // when one of the cursor is equal to 0
        if (targetCur == 0 || sourceCur == 0) {
            dpArr[sourceCur][targetCur] = targetCur + sourceCur;
            continue;
        }
        // check last alphabet
        lastAlphabetNotEqual = 1;
        if (caseData.source[sourceCur - 1] == caseData.target[targetCur - 1]) {
            lastAlphabetNotEqual = 0;
        };
        // dpArr value candidate
        valueWhenUseLast = dpArr[sourceCur - 1][targetCur - 1] + lastAlphabetNotEqual;
        valueWhenNotUseLast = dpArr[sourceCur - 1][targetCur] + 1;
        valueWhenAddLast = dpArr[sourceCur][targetCur - 1] + 1;
        // update dpArr
        dpArr[sourceCur][targetCur] = min({valueWhenUseLast, valueWhenNotUseLast, valueWhenAddLast});
    }
}

Time Complexity Analysis

Based on the dp iteration part, we can easily know this algorithm has an $O(mn)$ time complexity. (In which $m$ and $n$ are the length of source and target string).