ARTS #023

ARTS 023

This is article 23

Algorihm algorithm question

72. Edit Distance

Difficulty Hard

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Example 1:

Example 2:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

I didn’t fully solve this question myself. Then I searched for the answer and found that dynamic programming was needed. I had never studied dynamic programming in depth before. I took this opportunity to study it carefully and found that dynamic programming is really not easy to understand. After reading it for two days, I found that I had just started. When learning dynamic programming, it is recommended to read “Algorithm Illustration” first. The explanation of dynamic programming in Algorithm Illustration is relatively easy to understand, and then search for information on the Internet to help you understand. Dynamic programming is not something that can be understood in one go. You still need to practice more.

Regarding this algorithm question, this one is relatively okay: https://blog.csdn.net/pipisorry/article/details/46383947

In addition to dynamic programming, this problem can also be solved recursively.

Solution

Language: C

static inline int min(int a, int b)
{
    return a < b ? a : b;
}

 int minDistance(char* word1, char* word2)
{
    int i, j;
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int *table = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    int **dp = malloc((len1 + 1) * sizeof(int *));
    for (i = 0; i < len1 + 1; i++) {
        dp[i] = table + i * (len2 + 1);
    }
    
    for (i = 0; i < len2 + 1; i++) {
        dp[0][i] = i;
    }
    for (i = 0; i < len1 + 1; i++) {
        dp[i][0] = i;
    }
    
    for (i = 1; i < len1 + 1; i++) {
        for (j = 1; j < len2 + 1; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
            }
            

        }
    }
    return dp[len1][len2];
}

Review

This article mainly introduces several key programming knowledge that programming beginners should master: https://dandan2009.github.io/2019/01/25/the-main-pillars-of-learning-programming/

TIPS

This week we sorted out the principles of asymmetric encryption, https, and iOSAPP signatures: https://dandan2009.github.io/2019/01/24/certificate-rsa/

Share

As an iOS developer, you still need to keep practicing algorithms. In addition to algorithms, you still need to catch up on basic computer-related knowledge. Although in most of the development, we use the system that is directly encapsulated, and we rarely encounter situations where we write algorithms and networks by ourselves. The reason why you rarely encounter it is because you are still on the surface and do not go deep enough. For example, to optimize iOS, you need to understand things related to the operating system, and you need to look at some excellent codes and the implementation of underlying source code. If you do not master basic knowledge of algorithms and computers, you will find that iOS optimization cannot be done. So I think any programmer should learn computer basics, which are things in our university courses, such as computer operating systems, computer networks, algorithms and data structures. It’s not that these things are useless, but you are still on the surface of programming and have not gone deep into it.