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