ARTS 023
这是第23篇
Algorihm 算法题
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')
这道题自己也没完全做出来，后来搜索了下答案，发现要用动态规划，之前一直没有深入学习过动态规划，趁着这次机会好好学习一下，发现动态规划确实不容易理解，看了两天发现才刚入门。 在学习动态规划的时候建议先看下《算法图解》，算法图解中动态规划讲解的还是比较易懂的，然后再到网上搜一搜资料帮助理解，动态规划也不是一下就能吃透的，还是要多练习。
关于这道算法题， 这个讲的相对还可以：https://blog.csdn.net/pipisorry/article/details/46383947
这道题除了用动态规划还可以用递归解法。
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
本文主要介绍了编程初学者应该掌握的几个编程的重点知识： https://dandan2009.github.io/2019/01/25/the-main-pillars-of-learning-programming/
TIPS
本周对非对称加密、https、 iOSAPP签名原理进行了梳理: https://dandan2009.github.io/2019/01/24/certificate-rsa/
Share
作为一名iOS开发着，算法还是要坚持练习的，除了算法，计算机相关的基础知识还是要再补一下。尽管在大部分开发中，我们用到的都是系统直接封装好的，很少遇到自己写算法，写网络的情况。你之所以很少遇到，是因为你还停留在表面，做的不够深入， 比如iOS的优化，就需要了解操作系统相关的东西， 需要看一些优秀的代码和底层源码的实现， 如果不掌握算法和计算机基础知识，你就会发现，iOS优化做不下去。 所以我觉得任何程序员，都应该学习计算机基础的东西，也就是我们大学课程的东西，比如计算机操作系统，计算机网络，算法与数据结构，这些东西不是用不到，而是你还停留在编程的表面，没有深入进去。
-
Previous
非对称加密、https、 iOSAPP签名原理 -
Next
The main pillars of learning programming — and why beginners should master them.
