一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
查看: 279|回复: 3
收起左侧

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

[复制链接] |只看干货 |动态规划, 刷题
我的人缘0

升级   4.86%


分享帖子到朋友圈
miawallace | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   85% (29)
 
 
14% (5)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
在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

我的代码:

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


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

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

评分

参与人数 1大米 +6 收起 理由
14417335 + 6

查看全部评分


上一篇:关于Leetcode会员购买和自动续费
下一篇:找实习为目标,刷题重点应该放在什么上面呢?
我的人缘0

升级   20.43%

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]嘛
回复

使用道具 举报

我的人缘0

升级   86.67%

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
回复

使用道具 举报

我的人缘0

升级   2%

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表