[Solved] String Distance Contest Problem

String Distance: You are given two strings, ‘S’ and ‘T’, consisting of lowercase English characters.

Given a string ‘A’, we can modify the string to add any number of space characters at the beginning, end, or anywhere in between the string. Let’s call the modified string ‘MA’.

You modify the string ‘S’ and ‘T’ to get ‘MS’ and ‘MT’ such that they are both of the same lengths. The distance between the two strings is the sum of the distances between the corresponding characters in the modified strings. The rule to find the distance between two characters is:

a) Distance between two lowercase English characters is the absolute difference between their ASCII codes.
b) Distance between a lowercase English character and a space character is a fixed value ‘K’.
c) Distance between two space characters is 0.

Your task is to find the minimum distance between the two strings ‘MS’ and ‘MT’. Note that you are given ‘S’ and ‘T’, and you can modify them to produce ‘MS’ and ‘MT’ such that the string distance is minimized.

String Distance Contest

Example :

S = “abc”, T = “ad”, K = 2
We can keep the string ‘S’ as it is and add a space character between the characters ‘a’ and ‘d’ in the string ‘T’. So ‘MS’ = “abc”, and ‘MT’ = “a d”. The string distance is 0 + 2 + 1 = 3.
Hence, the answer is 3.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains a string ‘S’ consisting of lowercase English characters without spaces.

The second line of each test case contains a string ‘T’ consisting of lowercase English characters without spaces.

The third line of each test case contains a single integer ‘K’ denoting the distance between a space character and a lowercase character.

Output Format :

For each test case, calculate the minimum distance between the two strings ‘S’ and ‘T’ after modifying (possibly not modifying).

Output for each test case will be printed on a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
1 ≤ len(S), len(T) ≤ 1000
1 ≤ K ≤ 10^4

Time limit: 1 sec

Sample Input 1 :

2
ddab
chheg
5
dbag
cbh
2

Sample Output 1 :

19
4

Explanation For Sample Input 1 :

For test case 1: 
The cost to combine a lowercase English character and a space character is 5. 
One way to modify string ‘S’ is to get “ddab “ and ‘T’ to get “chheg”. The string distance, in this case, is 1 + 4 + 7 + 3 + 5(for space) = 20.
One other way is to modify string ‘S’ to get “d dab” and ‘T’ to get “chheg”. The string distance, in this case, is 1 + 5 + 4 + 4 + 5 = 19.
It can be proved that the minimum distance is 19; hence we will print 19.

For test case 2:
The cost to combine a lowercase English character and a space character is 2.
One way is to modify string ‘S’ to get “dbag” and ‘T’ to get “cb h”. The string distance in this case is 1 + 0 + 2(for space) + 1 = 4.
It can be proved that the minimum distance is 4; hence we will print 4.

Sample Input 2 :

2
ihhbf
ebdifeg
4
cehdaj
kehfid
5

Sample Output 2 :

19
21

Solution

Approach 1

Recursive Approach

Approach: 

• Let the lengths of the strings ‘S’ and ‘T’ be ‘N’ and ‘M’, respectively.
• What are the possible characters the last character of the string ‘S’ can be mapped to? Either it is mapped with a space character or one of the string ‘T’ characters.
• Let D(‘S[0..N-1]’, ‘T[0..M-1]’) be the minimum string distance of the strings ‘S’ and ‘T’.
  • If the last character of ‘S’ is mapped with a space character, we need to pay a cost of ‘K’ and so D(‘S[0..N-1]’, ‘T[0..M-1]’) = ‘K’ + D(S[0..N-2], T[0..M-1]).
  • If the last character of ‘T’ is mapped with a space character, we need to pay a cost of ‘K’ and so D(‘S[0..N-1]’, ‘T[0..M-1]’) = ‘K’ + D(S[0..N-1], T[0..M-2]).
  • If the last characters of ‘S’ and ‘T’ are mapped to each other, we need to pay ABS(‘S[N – 1]’ – ‘T[M – 1]’) cost and so D(‘S[0..N-1]’, ‘T[0..M-1]’) = ABS(‘S[N – 1]’ – ‘T[M – 1]’) + D(‘S[0..N-2]’, ‘T[0..M-2]’).
• These are the only cases possible for the last characters of the strings ‘S’ and ‘T’.
• If you have solved the Longest Common Subsequence (LCS Problem) before, these transitions may look familiar to you.

Algorithm: 

• Declare two variables, ‘n’ and ‘m’ and set them to the lengths of the strings ‘S’ and ‘T’.
• Create a helper function miniumStringDistanceHelper(‘i’, ‘j’, ‘k’, ‘s’, ‘t’). Here, ‘i’, ‘j’ is the state for which we want the answer, and, ‘k’, ‘s’, and ‘t’ are defined in the problem. Remember that ‘s’ and ‘t’ should be passed by reference and not by value to avoid unnecessary copying.
• Inside the function, first, we will handle the base cases.
• If ‘j’ == ‘0’, then return ‘i’ * ‘k’.
• If ‘i’ == ‘0’, then return ‘j’ * ‘k’.
• Return min({‘miniumStringDistanceHelper(‘i – 1’, ‘j’, ‘k’, ‘s’, ‘t’)’ + ‘k’, ‘miniumStringDistanceHelper(‘i’, ‘j – 1’, ‘k’, ‘s’, ‘t’)’ + ‘k’, ‘miniumStringDistanceHelper(‘i – 1’, ‘j – 1’, ‘k’, ‘s’, ‘t’)’ + abs(‘s[i – 1]’ – ‘t[j – 1]’)}).
• In the main function, we will call miniumStringDistanceHelper(‘n’, ’m’, ‘k’, ‘s’, ‘t’) and return this value.

Time Complexity

O(3 ^ (N + M)), where ‘N’ is the length of the string ‘S’ and ‘M’ is the length of the string ‘T’.

The recurrence equation is T(‘N’, ‘M’) = T(‘N – 1’, ‘M’) + T(‘N’, ‘M – 1’) + T(‘N – 1’, ‘M – 1’) + c. Although the exact solution for the above equation is through generating functions, it’s unnecessary, and an upper bound can easily be observed as the solution is exponential.

Hence, the time complexity is O(3 ^ (N + M)).

Space Complexity

O(max(N, M)), where ‘N’ is the length of the string ‘S’ and ‘M’ is the length of the string ‘T’.

The maximum depth of the recursive function can be max(‘N’, ‘M’). So, the stack space used is max(‘N’, ‘M’).

Hence, the space complexity is O(max(N, M)).

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N * M)

    where 'N' and 'M' denotes the length of the String 'S',
    and the String 'T' respectively.
*/	

public class Solution {

	private static String s, t;
	private static int minimumStringDistanceHelper(int i, int j, int k) {

		// Taking the prefix [0, 'i - 1'] of the String 's' and empty prefix of the String 't'.
		if (j == 0) {
			return i * k;
		}
	
		// Taking the prefix [1, 'j - 1'] of the String 't' and empty prefix of the String 's'.
		if (i == 0) {
			return j * k;
		}
		/*
		 * 3 cases:
		 * Combine 's[i - 1]' with a space character,
		 * Combine 't[j - 1]' with a space character,
		 * or combine both 's[i - 1]' and 't[j - 1]' together.
		 */
		return Math.min(Math.min(minimumStringDistanceHelper(i - 1, j, k) + k,
						minimumStringDistanceHelper(i, j - 1, k) + k),
						minimumStringDistanceHelper(i - 1, j - 1, k) + Math.abs(s.charAt(i - 1)- t.charAt(j - 1)));
	}

	public static int minimumStringDistance(String ss, String tt, int k) {

		// 'n' is the length of the String 's' and 'm' is the length of String 't'.
		s = ss;
		t = tt;
		int n = s.length(), m = t.length();
		return minimumStringDistanceHelper(n, m, k);
	}

}

/*
    Time Complexity: O(3 ^ (N + M))
    Space Complexity: O(max(N, M))

    where 'N' and 'M' denotes the length of the string 'S',
    and the string 'T' respectively.
*/

int minimumStringDistanceHelper(int i, int j, int k, string &s, string &t) {

    // Taking the prefix [0, 'i - 1'] of the string 's' and empty prefix of the string 't'.
    if (j == 0) {
        return i * k;
    }

    // Taking the prefix [1, 'j - 1'] of the string 't' and empty prefix of the string 's'.
    if (i == 0) {
        return j * k;
    }

    /*
     * 3 cases:
     * Combine 's[i - 1]' with a space character,
     * Combine 't[j - 1]' with a space character,
     * or combine both 's[i - 1]' and 't[j - 1]' together.
     */
    return min({minimumStringDistanceHelper(i - 1, j, k, s, t) + k,
                    minimumStringDistanceHelper(i, j - 1, k, s, t) + k,
                    minimumStringDistanceHelper(i - 1, j - 1, k, s, t) + abs(s[i - 1] - t[j - 1])});
}

int minimumStringDistance(string s, string t, int k) {

    // 'n' is the length of the string 's' and 'm' is the length of string 't'.
    int n = s.length(), m = t.length();

    return minimumStringDistanceHelper(n, m, k, s, t);
}

"""
    Time Complexity: O(3 ^ (N + M))
    Space Complexity: O(max(N, M))

    where 'N' and 'M' denotes the length of the string 'S',
    and the string 'T' respectively.
"""


def minimumStringDistanceHelper(i, j, k, s, t, dp):

    # Taking the prefix [0, 'i - 1'] of the string 's' and empty prefix of the string 't'.
    if j == 0:
        return i * k

    # Taking the prefix [1, 'j - 1'] of the string 't' and empty prefix of the string 's'.
    if i == 0:
        return j * k

    """
     * 3 cases:
     * Combine 's[i - 1]' with a space character,
     * Combine 't[j - 1]' with a space character,
     * or combine both 's[i - 1]' and 't[j - 1]' together.
    """

    return min({minimumStringDistanceHelper(i - 1, j, k, s, t, dp) + k,
                minimumStringDistanceHelper(i, j - 1, k, s, t, dp) + k,
                minimumStringDistanceHelper(i - 1, j - 1, k, s, t, dp) + abs(ord(s[i - 1]) - ord(t[j - 1]))})


def minimumStringDistance(s, t, k):
    # 'n' is the length of the string 's' and 'm' is the length of string 't'.
    n = len(s)
    m = len(t)
    dp = []

    return minimumStringDistanceHelper(n, m, k, s, t, dp)

Approach 2

Optimal Memoization Approach

Approach: 
 

• Please refer to Approach 1 for the solution idea to the problem. In this approach, we will discuss the Dynamic Programming Memoization approach for this problem.
• We are solving this problem by its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we solve the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Hence, in this approach, we will eliminate the need for solving the same subproblem again and again.
• For example, consider ‘N’ = 3, ‘M’ = 4.
• When we call the function with the above ‘N’, ‘M’, it will call the functions again with the following three states [(3, 3), (2, 4), (2, 3)].
• For (3, 3), it will call (2, 3), (3, 2), (2, 2). As you can see, it will call the state (2, 3) again.
• So, we can establish a Dynamic Programming Memoization Solution. Refer to the algorithm section for implementation details.
   

Algorithm: 

• Declare two variables, ‘n’ and ‘m’ and set them to the lengths of the strings ‘S’ and ‘T’.
• Create a 2D ‘dp’ table of size ‘N + 1’ by ‘M + 1’. Here, ‘dp[i][j]’ stores the minimum string distance if we consider the prefix [0..’i’) of the string ‘S’ and the prefix [0..’j’) of the string ‘T’. Initialize all the states of the ‘dp’ table by ‘-1’.
• Create a helper function that will calculate the dynamic programming state’s value. The function name is miniumStringDistanceHelper(‘i’, ‘j’, ‘k’, ‘s’, ‘t’, ‘dp’). Here, ‘i’, ‘j’ is the state for which we want the answer, ‘k’, ‘s’, and ‘t’ are defined in the problem, and ‘dp’ is the dynamic programming table. Remember that ‘s’ and ‘t’ should be passed by reference and not by value to avoid unnecessary copying.
• Inside the function, first, we will handle the base cases.
• If ‘j’ == ‘0’, then return ‘i’ * ‘k’.
• If ‘i’ == ‘0’, then return ‘j’ * ‘k’.
• If ‘dp[i][j] != -1’, it means we already computed this state, so return ‘dp[i][j]’.
• Assign ‘dp[i][j]’ = min({‘miniumStringDistanceHelper(‘i – 1’, ‘j’, ‘k’, ‘s’, ‘t’, ‘dp’)’ + ‘k’, ‘miniumStringDistanceHelper(‘i’, ‘j – 1’, ‘k’, ‘s’, ‘t’, ‘dp’)’ + ‘k’, ‘miniumStringDistanceHelper(‘i – 1’, ‘j – 1’, ‘k’, ‘s’, ‘t’, ‘dp’)’ + abs(‘s[i – 1]’ – ‘t[j – 1]’)}).
• Finally, return the value of ‘dp[i][j]’.
• In the main function, we will call miniumStringDistanceHelper(‘n’, ’m’, ‘k’, ‘s’, ‘t’, ‘dp’) and return this value.

Time Complexity

O(N * M), where ‘N’ is the length of the string ‘S’ and ‘M’ is the length of the string ‘T’.

Each state (‘i’, ‘j’), 0 ≤ ‘i’ ≤ N, 0 ≤ ‘j’ ≤ ‘M’, can be visited by at most 3 distinct cells.

Hence, the time complexity is O(N * M).

Space Complexity

O(N * M), where ‘N’ is the length of the string ‘S’ and ‘M’ is the length of the string ‘T’.

We create a 2D ‘dp’ table of the size ‘N + 1’ by ‘M + 1’.

Hence, the space complexity is O(N * M).

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N * M)

    where 'N' and 'M' denotes the length of the String 'S',
    and the String 'T' respectively.
*/	

public class Solution {

	private static String s, t;
	private static int minimumStringDistanceHelper(int i, int j, int k) {

		// Taking the prefix [0, 'i - 1'] of the String 's' and empty prefix of the String 't'.
		if (j == 0) {
			return i * k;
		}
	
		// Taking the prefix [1, 'j - 1'] of the String 't' and empty prefix of the String 's'.
		if (i == 0) {
			return j * k;
		}
		/*
		 * 3 cases:
		 * Combine 's[i - 1]' with a space character,
		 * Combine 't[j - 1]' with a space character,
		 * or combine both 's[i - 1]' and 't[j - 1]' together.
		 */
		return Math.min(Math.min(minimumStringDistanceHelper(i - 1, j, k) + k,
						minimumStringDistanceHelper(i, j - 1, k) + k),
						minimumStringDistanceHelper(i - 1, j - 1, k) + Math.abs(s.charAt(i - 1)- t.charAt(j - 1)));
	}

	public static int minimumStringDistance(String ss, String tt, int k) {

		// 'n' is the length of the String 's' and 'm' is the length of String 't'.
		s = ss;
		t = tt;
		int n = s.length(), m = t.length();
		return minimumStringDistanceHelper(n, m, k);
	}

}

"""
    Time Complexity: O(N * M)
    Space Complexity: O(N * M)

    where 'N' and 'M' denotes the length of the string 'S',
    and the string 'T' respectively.
"""


def minimumStringDistanceHelper(i, j, k, s, t, dp):

    # Taking the prefix [0, 'i - 1'] of the string 's' and empty prefix of the string 't'.
    if j == 0:
        return i * k

    # Taking the prefix [1, 'j - 1'] of the string 't' and empty prefix of the string 's'.
    if i == 0:
        return j * k

    # If we already computed this state, return the value.
    if dp[i][j] != -1:
        return dp[i][j]

    """
     * 3 cases:
     * Combine 's[i - 1]' with a space character,
     * Combine 't[j - 1]' with a space character,
     * or combine both 's[i - 1]' and 't[j - 1]' together.
    """

    dp[i][j] = min({minimumStringDistanceHelper(i - 1, j, k, s, t, dp) + k,
                    minimumStringDistanceHelper(i, j - 1, k, s, t, dp) + k,
                    minimumStringDistanceHelper(i - 1, j - 1, k, s, t, dp) + abs(ord(s[i - 1]) - ord(t[j - 1]))})

    # Return the answer 'dp[i][j]'.
    return dp[i][j]


def minimumStringDistance(s, t, k):
    # 'n' is the length of the string 's' and 'm' is the length of string 't'.
    n = len(s)
    m = len(t)

    """
     * 'dp[i][j]' stores the minimum string distance if
     *  we consider the prefix [0, 'i - 1'] of the string 's' and
     *  the prefix [0, 'j - 1'] of the string 't'.
    """

    dp = [[-1] * (m + 1) for _ in range(n + 1)]
    return minimumStringDistanceHelper(n, m, k, s, t, dp)

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N * M)

    where 'N' and 'M' denotes the length of the string 'S',
    and the string 'T' respectively.
*/

int minimumStringDistanceHelper(int i, int j, int k, string &s, string &t, vector<vector<int>> &dp) {

    // Taking the prefix [0, 'i - 1'] of the string 's' and empty prefix of the string 't'.
    if (j == 0) {
        return i * k;
    }

    // Taking the prefix [1, 'j - 1'] of the string 't' and empty prefix of the string 's'.
    if (i == 0) {
        return j * k;
    }

    // If we already computed this state, return the value.
    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    /*
     * 3 cases:
     * Combine 's[i - 1]' with a space character,
     * Combine 't[j - 1]' with a space character,
     * or combine both 's[i - 1]' and 't[j - 1]' together.
     */
    dp[i][j] = min({minimumStringDistanceHelper(i - 1, j, k, s, t, dp) + k,
                    minimumStringDistanceHelper(i, j - 1, k, s, t, dp) + k,
                    minimumStringDistanceHelper(i - 1, j - 1, k, s, t, dp) + abs(s[i - 1] - t[j - 1])});

    // Return the answer 'dp[i][j]'.
    return dp[i][j];
}

int minimumStringDistance(string s, string t, int k) {

    // 'n' is the length of the string 's' and 'm' is the length of string 't'.
    int n = s.length(), m = t.length();

    /*
     * 'dp[i][j]' stores the minimum string distance if
     *  we consider the prefix [0, 'i - 1'] of the string 's' and
     *  the prefix [0, 'j - 1'] of the string 't'.
     */
    vector<vector<int>> dp(n + 1, vector<int> (m + 1, -1));

    return minimumStringDistanceHelper(n, m, k, s, t, dp);
}

Approach 3

Optimal Iterative Approach

Approach: 

• Please refer to Approach 2 for the solution idea to the problem. In this approach, we will discuss the iterative dynamic programming approach for this problem.

Algorithm: 
 

• Declare two variables, ‘n’ and ‘m’ and set them to the lengths of the strings ‘S’ and ‘T’.
• Create a 2D ‘dp’ table of size ‘N + 1’ by ‘M + 1’. Here, ‘dp[i][j]’ stores the minimum string distance if we consider the prefix [0..’i’) of the string ‘S’ and the prefix [0..’j’) of the string ‘T’.
• Iterate over the prefix length of the string ‘S’ from ‘1’ to ‘N’ and set the value of ‘dp[i][0]’ = ‘i’ * ‘K’. Here ‘i’ is the iterating variable.
• Iterate over the prefix length of the string ‘T’  from ‘1’ to ‘M’ and set the value of ‘dp[0][j]’ = ‘j’ * ‘K’. Here ‘j’ is the iterating variable.
• Iterate over the prefix length of the string ‘S’ from ‘1’ to ‘N’. Then, Iterate over the prefix length of the string ‘T’ from ‘1’ to ‘M’. Let the iterating variables be ‘i’ and ‘j’.
• Assign ‘dp[i][j]’ = min({‘dp[i – 1][j]’ + ‘k’, ‘dp[i][j – 1]’ + ‘k’, ‘dp[i – 1][j – 1]’ + abs(‘s[i – 1]’ – ‘t[j – 1]’)}).
• Finally, return the value of ‘dp[n][m]’.

Time Complexity

O(N * M), where ‘N’ is the length of the string ‘S’ and ‘M’ is the length of the string ‘T’.

We create two for loops and iterate through ‘1’ to ‘N’ in one loop and ‘1’ to ‘M’ in another loop. 

Hence, the time complexity is O(N * M).

Space Complexity

O(N * M), where ‘N’ is the length of the string ‘S’ and ‘M’ is the length of the string ‘T’.
 

We create a 2D ‘dp’ table of the size ‘N + 1’ by ‘M + 1’.

Hence, the space complexity is O(N * M).

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N * M)

    where 'N' and 'M' denotes the length of the String 'S',
    and the String 'T' respectively.
*/	

public class Solution {

	private static String s, t;
	private static int minimumStringDistanceHelper(int i, int j, int k) {

		// Taking the prefix [0, 'i - 1'] of the String 's' and empty prefix of the String 't'.
		if (j == 0) {
			return i * k;
		}
	
		// Taking the prefix [1, 'j - 1'] of the String 't' and empty prefix of the String 's'.
		if (i == 0) {
			return j * k;
		}
		/*
		 * 3 cases:
		 * Combine 's[i - 1]' with a space character,
		 * Combine 't[j - 1]' with a space character,
		 * or combine both 's[i - 1]' and 't[j - 1]' together.
		 */
		return Math.min(Math.min(minimumStringDistanceHelper(i - 1, j, k) + k,
						minimumStringDistanceHelper(i, j - 1, k) + k),
						minimumStringDistanceHelper(i - 1, j - 1, k) + Math.abs(s.charAt(i - 1)- t.charAt(j - 1)));
	}

	public static int minimumStringDistance(String ss, String tt, int k) {

		// 'n' is the length of the String 's' and 'm' is the length of String 't'.
		s = ss;
		t = tt;
		int n = s.length(), m = t.length();
		return minimumStringDistanceHelper(n, m, k);
	}

}

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N * M)

    where 'N' and 'M' denotes the length of the string 'S',
    and the string 'T' respectively.
*/

int minimumStringDistance(string s, string t, int k) {

    // 'n' is the length of the string 's' and 'm' is the length of string 't'.
    int n = s.length(), m = t.length();

    /*
     * 'dp[i][j]' stores the minimum string distance if
     *  we consider the prefix [0, 'i - 1'] of the string 's' and
     *  the prefix [0, 'j - 1'] of the string 't'.
     */
    vector<vector<int>> dp(n + 1, vector<int> (m + 1));

    // Taking the prefix [0, 'i - 1'] of the string 's' and empty prefix of the string 't'.
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = i * k;
    }

    // Taking the prefix [1, 'j - 1'] of the string 't' and empty prefix of the string 's'.
    for (int j = 1; j <= m; ++j) {
        dp[0][j] = j * k;
    }

    // Iterate over the prefix of 's'.
    for (int i = 1; i <= n; ++i) {

        // Iterate over the prefix of 't'.
        for (int j = 1; j <= m; ++j) {

            /*
             * 3 cases:
             * Combine 's[i - 1]' with a space character,
             * Combine 't[j - 1]' with a space character,
             * or combine both 's[i - 1]' and 't[j - 1]' together.
             */
            dp[i][j] = min({dp[i - 1][j] + k, dp[i][j - 1] + k, dp[i - 1][j - 1] + abs(s[i - 1] - t[j - 1])});
        }
    }

    // Return the answer 'dp[n][m]'.
    return dp[n][m];
}

"""
    Time Complexity: O(N * M)
    Space Complexity: O(N * M)

    where 'N' and 'M' denotes the length of the string 'S',
    and the string 'T' respectively.
"""


def minimumStringDistance(s, t, k):

    # 'n' is the length of the string 's' and 'm' is the length of string 't'.
    n = len(s)
    m = len(t)

    """
     * 'dp[i][j]' stores the minimum string distance if
     *  we consider the prefix [0, 'i - 1'] of the string 's' and
     *  the prefix [0, 'j - 1'] of the string 't'.
    """

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # Taking the prefix [0, 'i - 1'] of the string 's' and empty prefix of the string 't'.
    for i in range(1, n + 1):
        dp[i][0] = i * k

    # Taking the prefix [1, 'j - 1'] of the string 't' and empty prefix of the string 's'.
    for j in range(1, m + 1):
        dp[0][j] = j * k

    # Iterate over the prefix of 's'.
    for i in range(1, n + 1):

        # Iterate over the prefix of 't'.
        for j in range(1, m + 1):
            """
             * 3 cases:
             * Combine 's[i - 1]' with a space character,
             * Combine 't[j - 1]' with a space character,
             * or combine both 's[i - 1]' and 't[j - 1]' together.
            """
            dp[i][j] = min(dp[i - 1][j] + k, dp[i][j - 1] + k, dp[i - 1][j - 1] + abs(ord(s[i - 1]) - ord(t[j - 1])))

    # Return the answer 'dp[n][m]'.
    return dp[n][m]

Happy Learning – If you require any further information, feel free to contact me.