登录
  • #刷题
  • #动态规划

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

miawallace
340
3
在Pramp上做了一道和edit distance类似的题。后面我写了我的javascript代码,但是有些edge case就是过不去。

有没有哪个大神可以指点一下这个题怎么做的

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[0] = i

}

for(let j = 0; j <= source.length; j++) {

dp[0][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]

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

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

我的答案是 ["C","'+A","+B","+A","+A","B","B","C"]
3条回复
热度排序

发表回复