知识卡片

普通读书笔记卡 · 5654.c.3.b.3.a.1.b

编辑距离按两个前缀做决策

理解等级:中级

状态表示把第一序列前i项改为第二序列前j项的最少步数。末项相同就沿对角继承,否则在插入、删除、替换三种来源中取最小再加1;空前缀需要插入或删除全部已有项。

这里每种操作代价都是1,比较单位必须一致。原书后续Go版用字符串字节索引,因此直接实现的是字节编辑距离;Unicode码点或用户字素距离需先明确分割方式,不能把len(string)当字符数。

实现以dp[i][0]=i、dp[0][j]=j初始化空前缀边界,按行列正序计算;相等直接取左上旧值,不相等取三来源最小加1。实际s[i-1]/t[j-1]为字节比较,不能把本例单位擅称Unicode字符。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      每一轮的决策是对字符串 进行一次编辑操作。 −1] − 1] 我们希望在编辑操作的过程中,问题的规模逐渐缩小,这样才能构建子问题。设字符串 和 的长度分别为 和 ,我们先考虑两字符串尾部的字符−1] −1] 和 。 −2

    • · 查看原书依据

      func editDistanceDP(s string, t string) int { n := len(s ) m := len(t ) dp := make([][]int, n+1 ) for i := 0;

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[29475,29585)) - 结论依据:实际前缀状态与三编辑来源及相等继承,限定单位和代价。 - 原始内容:每一轮的决策是对字符串 进行一次编辑操作。 −1] − 1] 我们希望在编辑操作的过程中,问题的规模逐渐缩小,这样才能构建子问题。设字符串 和 的长度分别为 和 ,我们先考虑两字符串尾部的字符−1] −1] 和 。 −2 补充原书证据:spine 7 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/8.html;归一字符[243,352)。 - 结论依据:实际完整代码补齐边界和字节单位。 - 原始内容:func editDistanceDP(s string, t string) int { n := len(s ) m := len(t ) dp := make([][]int, n+1 ) for i := 0;