Editorial for Mystic Move

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

English

This question is about Levenshtein Distance. The question can be solved by using recursive or dynamic programming algorithm. Since direct recursive solution can be problematic in terms of complexity, we can use the dynamic programming algorithm.

Türkçe

Bu soru Levenshtein Distance ile ilgilidir. Soru recursive veya dinamik programlama algoritması kullanılarak çözülebilir. Doğrudan recursive çözüm complexity açısından sorunlu olabileceğinden dinamik programlama algoritmasını kullanabiliriz.

Codes

C++

include <iostream>
#include <vector>
#include <algorithm>

int levenshteinDistance(const std::string& s1, const std::string& s2, int length1, int length2) {
    int len_s1 = length1 + 1;
    int len_s2 = length2 + 1;

    // Create a 2D vector to store the distances
    std::vector<std::vector<int>> distances(len_s1, std::vector<int>(len_s2, 0));

    // Initialize the first row and column
    for (int i = 0; i < len_s1; ++i) {
        distances[i][0] = i;
    }
    for (int j = 0; j < len_s2; ++j) {
        distances[0][j] = j;
    }

    // Fill the vector
    for (int i = 1; i < len_s1; ++i) {
        for (int j = 1; j < len_s2; ++j) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
            distances[i][j] = std::min({
                distances[i - 1][j] + 1,
                distances[i][j - 1] + 1,
                distances[i - 1][j - 1] + cost
            });
        }
    }

    return distances[len_s1 - 1][len_s2 - 1];
}

Python 3

def levenshtein_distance(s1: str, s2: str, len1: int, len2: int):
    len_s1 = len1 + 1
    len_s2 = len2 + 1

    # Create a 2D array to store the distances
    distances = [[0 for _ in range(len_s2)] for _ in range(len_s1)]

    # Initialize the first row and column
    for i in range(len_s1):
        distances[i][0] = i
    for j in range(len_s2):
        distances[0][j] = j

    # Fill the array
    for i in range(1, len_s1):
        for j in range(1, len_s2):
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            distances[i][j] = min(
                distances[i - 1][j] + 1,
                distances[i][j - 1] + 1,
                distances[i - 1][j - 1] + cost
            )

    return distances[len_s1 - 1][len_s2 - 1]


if __name__ == "__main__":
    len1, len2 = map(int, input().split())
    string1 = input()
    string2 = input()

    result = levenshtein_distance(string1, string2, len1, len2)
    print(result)