练习输入序列时,可以把遗漏、误按和多按分别理解为插入、替换和删除。最少操作数提供一种明确的差异度,但它与简单统计不同位置的字符数并不一样。
每次插入、删除或替换一个符号成本都为一,相同符号保留成本为零。表格横轴为目标前缀、纵轴为原序列前缀;每个格子比较左边加一、上边加一以及左上角加本次匹配成本。
原序列CCACA,目标序列DADACABB;符号仅为抽象按键编号。
目标前缀列:空串,D,DA,DAD,DADA,DADAC,DADACA,DADACAB,DADACABB 空串 | [0, 1, 2, 3, 4, 5, 6, 7, 8] C | [1, 1, 2, 3, 4, 4, 5, 6, 7] CC | [2, 2, 2, 3, 4, 4, 5, 6, 7] CCA | [3, 3, 2, 3, 3, 4, 4, 5, 6] CCAC | [4, 4, 3, 3, 4, 3, 4, 5, 6] CCACA | [5, 5, 4, 4, 3, 4, 3, 4, 5] 最少修改数:5。
表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。
空串到长度n的串需要n次插入,反向需要n次删除。最终数值位于两个完整前缀相交处,不能把整张表的数值相加;插入和删除会改变后续位置的对应关系。
这只是字符串编辑距离,不表示玩家实际反应时间或动作难度。若游戏允许一次交换相邻按键,或不同错误有不同成本,应修改操作集合和规则,不能继续套用本例的单位成本表。
练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。