求解Pramp上一道类似edit distance的DP题

在Pramp上做了一道和edit distance类似的题。后面我写了我的javascript代码，但是有些edge case就是过不去。
有没有哪个大神可以指点一下这个题怎么做的

Pramp 链接： https://www.pramp.com/challenge/5j2xWAx1qPtlZGLnG2O0
题目：
Diff Between Two Strings
Given two strings of uppercase letters source and target, list (in string form) a sequence of edits to convert from source to target that uses the least edits possible.

For example, with strings source = "ABCDEFG", and target = "ABDFFGH" we might return: ["A", "B", "-C", "D", "-E", "F", "+F", "G", "+H"

More formally, for each character C in source, we will either write the token C, which does not count as an edit; or write the token -C, which counts as an edit.

Additionally, between any token that we write, we may write +D where D is any letter, which counts as an edit.

At the end, when reading the tokens from left to right, and not including tokens prefixed with a minus-sign, the letters should spell out target (when ignoring plus-signs.)

In the example, the answer of A B -C D -E F +F G +H has total number of edits 4 (the minimum possible), and ignoring subtraction-tokens, spells out A, B, D, F, +F, G, +H which represents the string target.

If there are multiple answers, use the answer that favors removing from the source first.

Constraints:

[time limit] 5000ms
[input] string source
2 ≤ source.length ≤ 12
[input] string target
2 ≤ target.length ≤ 12
[output] array.string

我的代码:

1. function diffBetweenTwoStrings(source, target) {
   
2.   const dp = [...Array(target.length + 1)].map(row => Array(source.length + 1).fill(0))
   
3. 
   
4.   for(let i = 0; i <= target.length; i++) {
   
5.     dp[i][0] = i
   
6.   }
   
7. 
   
8.   for(let j = 0; j <= source.length; j++) {
   
9.     dp[0][j] = j
   
10.   }
    
11. 
    
12.   for(let j = 1; j <= source.length; j++) {
    
13.     for(let i = 1; i <= target.length; i++) {
    
14.       const row = i - 1
    
15.       const col = j - 1
    
16.       if(target[row] === source[col]) {
    
17.         dp[i][j] = dp[i-1][j-1] + 1
    
18.       } else {
    
19.         dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1
    
20.       }
    
21.     }
    
22.   }
    
23. 
    
24.   let ans = []
    
25.   let i = target.length
    
26.   let j = source.length
    
27. 
    
28.   while(i > 0 && j > 0) {
    
29.     if(target[i - 1] !== source[j - 1]) {
    
30.       if(dp[i - 1][j] <= dp[i][j-1]) {
    
31.         ans.unshift(`+${target[i - 1]}`)
    
32.         i--
    
33.       } else {
    
34.         ans.unshift(`-${source[j - 1]}`)
    
35.         j--
    
36.       }
    
37.     } else {
    
38.       ans.unshift(target[i-1])
    
39.       i--
    
40.       j--
    
41.     }
    
42. 
    
43.   }
    
44. 
    
45.   while(j > 0) {
    
46.     ans.unshift(`-${source[j-1]}`)
    
47.     j--
    
48.   }
    
49. 
    
50.   while(i > 0) {
    
51.     ans.unshift(`+${target[i-1]}`)
    
52.     i--
    
53.   }
    
54. 
    
55.   for(let idx = 0; idx < ans.length - 1; idx++) {
    
56.     if(ans[idx] === '+' + ans[idx + 1]) {
    
57.       let temp = ans[idx]
    
58.       ans[idx] = ans[idx + 1]
    
59.       ans[idx + 1] = temp
    
60.     }
    
61.   }
    
62.   return ans
    
63. }
    
64. console.log(diffBetweenTwoStrings("CBBC", "CABAABBC"))
    

复制代码

最后这个就是没过去的case，diffBetweenTwoStrings("CBBC", "CABAABBC")

标准答案是 ["C","+A","B","+A","+A","B","+B","C"]
我的答案是 ["C","'+A","+B","+A","+A","B","B","C"]

虽然我看不懂JS，但17行不应该是dp[i][j] = dp[i-1][j-1]嘛

line 17:  dp[i][j] = dp[i-1][j-1]
line 19: dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

这题就是 LCS，比方说 "ACC" 要变成 "ACB"

1. Ø A C B
   
2. ↖
   
3. A 1←1←1
   
4.   ↑↖
   
5. C 1 2←2
   
6.   ↑↖↑ ↑
   
7. C 1 2←2

复制代码

右下角到右上角一共3条路，对应着三种合法的序列
A C +B -C
A C -C +B
A -C C B

看题目要求应该是要尽量先往左走。