## 帐号 密码 自动登录 找回密码 注册账号
 搜索

# [动态规划] 求解Pramp上一道类似edit distance的DP题

|只看干货 |  miawallace | 显示全部楼层 |阅读模式
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   85% (29) 14% (5)    👎

### 注册一亩三分地论坛，查看更多干货！

x

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

[JavaScript] 纯文本查看 复制代码
```function diffBetweenTwoStrings(source, target) {
const dp = [...Array(target.length + 1)].map(row => Array(source.length + 1).fill(0))

for(let i = 0; i <= target.length; i++) {
dp[i] = i
}

for(let j = 0; j <= source.length; j++) {
dp[j] = j
}

for(let j = 1; j <= source.length; j++) {
for(let i = 1; i <= target.length; i++) {
const row = i - 1
const col = j - 1
if(target[row] === source[col]) {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1
}
}
}

let ans = []
let i = target.length
let j = source.length

while(i > 0 && j > 0) {
if(target[i - 1] !== source[j - 1]) {
if(dp[i - 1][j] <= dp[i][j-1]) {
ans.unshift(`+\${target[i - 1]}`)
i--
} else {
ans.unshift(`-\${source[j - 1]}`)
j--
}
} else {
ans.unshift(target[i-1])
i--
j--
}

}

while(j > 0) {
ans.unshift(`-\${source[j-1]}`)
j--
}

while(i > 0) {
ans.unshift(`+\${target[i-1]}`)
i--
}

for(let idx = 0; idx < ans.length - 1; idx++) {
if(ans[idx] === '+' + ans[idx + 1]) {
let temp = ans[idx]
ans[idx] = ans[idx + 1]
ans[idx + 1] = temp
}
}
return ans
}
console.log(diffBetweenTwoStrings("CBBC", "CABAABBC"))
```

### 评分 cjhcjj 2020-10-24 15:15:44 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (85) 0% (0)    👎
 虽然我看不懂JS，但17行不应该是dp[i][j] = dp[i-1][j-1]嘛 cozec2013 2020-10-27 08:06:02 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 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 usr_opta 2020-10-28 08:52:16 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (14) 0% (0)    👎
 这题就是 LCS，比方说 "ACC" 要变成 "ACB" [Bash shell] 纯文本查看 复制代码```Ø A C B ↖ A 1←1←1 ↑↖ C 1 2←2 ↑↖↑ ↑ C 1 2←2``` 右下角到右上角一共3条路，对应着三种合法的序列 A C +B -C A C -C +B A -C C B 看题目要求应该是要尽量先往左走。