 • #刷题
• #动态规划

# 求解Pramp上一道类似edit distance的DP题 miawallace
340
3

Pramp 链接： pramp.com

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"[br]
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

[mw_shl_code=javascript,true]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

}

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[j] = dp[i-1][j-1] + 1

} else {

dp[j] = Math.min(dp[i-1][j], dp[j-1]) + 1

}

}

}

let ans = [][br]
let i = target.length

let j = source.length

while(i > 0 && j > 0) {

if(target !== source[j - 1]) {

if(dp[j] <= dp[j-1]) {

ans.unshift(`+\${target}`)

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"))

[/mw_shl_code]

3条回复