算法
LeetCode T72. 编辑距离[1]
描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
1.插入一个字符2.删除一个字符3.替换一个字符
示例1
代码语言：javascript复制输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例2
代码语言：javascript复制输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')分析
很典型的动态规划问题，借助状态数数组存储每个子步骤状态。以 horse 、ros 为例，我们开辟一个二维数组，横向存放目标字符串各字符下标，纵向存放待处理字符串各字符下标，而后进行计算，计算规则与图示例如下，转自 LeetCode
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
代码
代码语言：javascript复制/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
let minDistance = (word1, word2) => {
let n = word1.length, m = word2.length
let dp = new Array(n 1).fill(0).map(() => new Array(m 1).fill(0))
for (let i = 0; i <= n; i ) {
dp[i][0] = i
}
for (let j = 0; j <= m; j ) {
dp[0][j] = j
}
for (let i = 0; i <= n; i ) {
for (let j = 0; j <= m; j ) {
if (i * j) {
dp[i][j] = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] : (Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) 1)
} else {
dp[i][j] = i j
}
}
}
return dp[n][m]
};前端
Redux的reducer为什么不能有副作用的操作
Redux的设计参考了Flux的模式，作者希望以此来实现时间旅行，保存应用的历史状态，实现应用状态的可预测。所以整个Redux都是函数式编程的范式，要求reducer 是 纯函数 也是自然而然的事情，使用纯函数才能保证相同的输入得到相同的输入，保证状态的可预测。所以Redux有三大原则：
•单一数据源state•state 只读，Redux没有暴露出直接修改state的接口，必须通过action来触发修改•使用纯函数来修改state，reducer必须是纯函数
代码语言：javascript复制currentState = currentReducer(currentState, action)currentReducer 就是我们在 createStore 中传入的 reducer，reducer 用来计算state的，所以它的返回值必须是 state ，也就是我们整个应用的状态，而不能是 promise之类的。
要在reducer中加入异步的操作，如果你只是单纯想执行异步操作，不会等待异步的返回，那么在reducer中执行的意义是什么。如果想把异步操作的结果反应在state中，首先整个应用的状态将变的不可预测，违背Redux的设计原则，其次，此时的currentState将会是promise之类而不是我们想要的应用状态，根本是行不通的。
References
[1] 72. 编辑距离: https://leetcode-cn.com/problems/edit-distance/
