一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 2342|回复: 14
收起左侧

edit distance to palindrome snapchat面经题

[复制链接] |试试Instant~ |关注本帖
cdefgh3000 发表于 2016-10-13 07:54:04 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Snapchat - 内推 - Onsite |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
想问一道Snapchat的onsite的

edit distance to palindrome. The cost of add remove and replace are both 1.
多谢
ericlee27 发表于 2016-10-14 06:35:53 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
小A要当码农 发表于 2016-10-14 05:02
这题不能直接DP么。。。?

直接DP的话 要怎么做呀?
回复 支持 1 反对 0

使用道具 举报

ericlee27 发表于 2016-10-13 08:20:23 | 显示全部楼层
关注一亩三分地微博:
Warald
这道题你把这个字符串翻转过来做EDIT DISTANCE 沿着从左下到右上的对角线找,如果是偶数长度,只找对角线,奇数长度,找对角线上下各一格。最后MIN就是结果。
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-10-13 08:24:27 | 显示全部楼层
  1.     public static void main(String[] args) {
  2.         String a = "czzasc";
  3.         StringBuilder sb = new StringBuilder(a);
  4.         String b = sb.reverse().toString();. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.         System.out.print(minDistance(a, b));
  6.     }
  7. .1point3acres缃
  8.     public static int minDistance(String word1, String word2) {
  9.         int length1 = word1.length();
  10.         int length2 = word2.length();
  11.         if (length1 == 0 || length2 == 0) return Math.max(length1, length2);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.         int[][] dp = new int[length1 + 1][length2 + 1];
  13.         dp[0][0] = 0;
  14.         for (int i = 1; i <= length1; ++i) {
  15.             dp[i][0] = i;. 鍥磋鎴戜滑@1point 3 acres
  16.         }
  17.         for (int j = 1; j <= length2; ++j) {
  18.             dp[0][j] = j;
  19.         }

  20.         // DP
  21.         for (int i = 1; i <= length1; ++i) {. 1point 3acres 璁哄潧
  22.             for(int j = 1; j <= length2; ++j) {.1point3acres缃
  23.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  24.                     dp[i][j] = dp[i - 1][j - 1];
  25.                 } else {
  26.                     dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
    . more info on 1point3acres.com
  27.                 }-google 1point3acres
  28.             }
  29.         }
  30.         int minEdit = Integer.MAX_VALUE;
  31.         int x = 0;
  32.         int y = word1.length();
  33.         while (x <= length2 && y >= 0) {
  34.             int diagnoal = dp[y][x];
  35.             int top = y >= 1 ? dp[y - 1][x] : Integer.MAX_VALUE;
  36.             int bottom = y < length1 ? dp[y + 1][x] : Integer.MAX_VALUE;
  37.             int smallest = Math.min(diagnoal, Math.min(top, bottom));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  38.             minEdit = Math.min(smallest, minEdit);
  39.             x++;
  40.             y--;
  41.         }
  42.         return minEdit;
  43.     }
复制代码
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-14 05:02:36 | 显示全部楼层

这题不能直接DP么。。。?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

sqz2017er 发表于 2016-10-14 07:21:29 | 显示全部楼层
ericlee27 发表于 2016-10-14 06:35
直接DP的话 要怎么做呀?

一个问题,既然我看到po的code,既然已经 dp 到 最后了,为什么不直接return dp[length1][length2]?
回复 支持 反对

使用道具 举报

翔在天空 发表于 2016-10-14 08:09:57 | 显示全部楼层

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴po 主为什么不知道返回最后一项呢
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-14 09:51:35 | 显示全部楼层
ericlee27 发表于 2016-10-13 08:20
这道题你把这个字符串翻转过来做EDIT DISTANCE 沿着从左下到右上的对角线找,如果是偶数长度,只找对角线, ...

dp[j]是s.charAt(i)到s.charAt(j)之间的minDistance啊... if (s.charAt(i) == s.charAt(j)) dp[j] = dp[i + 1][j - 1]. else dp[j] = Math.min(dp[i + 1][j - 1]), Math.min(dp[j - 1], dp[i + 1][j])) + 1 ?
回复 支持 反对

使用道具 举报

lfzh123 发表于 2016-11-28 03:30:26 | 显示全部楼层
ericlee27 发表于 2016-10-13 08:20
这道题你把这个字符串翻转过来做EDIT DISTANCE 沿着从左下到右上的对角线找,如果是偶数长度,只找对角线, ...

感谢分享code。能解释一下逻辑吗?
我在overstack上面看到一个算法,觉得挺对的。
http://stackoverflow.com/questio ... removals-of-charact. From 1point 3acres bbs
Let dp[i, j] = minimum number of removals needed to convert the substring [i, j] to a palindrome
dp[i, j] = dp[i + 1, j - 1]                     # if a == a[j]
           min(dp[i + 1, j], dp[i, j - 1]) + 1  # otherwise
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-11-29 15:26:16 | 显示全部楼层

初始化的地方明显不对

dp[0][j]=j 显然不对
也许已经就是palindrome,或者只差一个或几个呢
回复 支持 反对

使用道具 举报

kin332026 发表于 2016-11-30 02:21:20 | 显示全部楼层
大家看下,可以这样吗?

  1. public int minEdit(String s) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  2.         int length = s.length();
  3.         int[][] dp = new int[length][length];
  4.         char[] inputs = s.toCharArray();
  5.         for (int i = 1; i < length; i++) {
  6.             int l = 0, r = i;
  7.             while (r < length) {
    . From 1point 3acres bbs
  8.                 if (inputs[l] == inputs[r]) {
  9.                     dp[l][r] = dp[l + 1][r - 1];
  10.                 } else {
  11.                     dp[l][r] = Math.min(dp[l + 1][r - 1], Math.min(dp[l + 1][r], dp[l][r - 1])) + 1;. From 1point 3acres bbs
  12.                 }
  13.                 l++;
  14.                 r++;
  15.             }
  16.         }
  17.         return dp[0][length - 1];
  18.     }
复制代码
回复 支持 反对

使用道具 举报

glad2mu 发表于 2016-12-15 07:26:11 | 显示全部楼层
这道题 把string reverse一下然后按edit distance 那题做,这种做法对么? 如果对的话 怎么证明一定是minimum的?
回复 支持 反对

使用道具 举报

zhhan1990 发表于 2016-12-31 08:55:10 | 显示全部楼层
翔在天空 发表于 2016-10-14 08:09
po 主为什么不知道返回最后一项呢

我感觉返回最后一项/2就好了
回复 支持 反对

使用道具 举报

zhhan1990 发表于 2016-12-31 08:57:00 | 显示全部楼层
freemail165 发表于 2016-11-29 15:26
初始化的地方明显不对

. from: 1point3acres.com/bbs dp[0][j]=j 显然不对

结果和初始化没有必然关系,因为(0,0)点肯定是0,然后如果本身是palidrome的话那么对角线都是0,最后只要返回(n,n) 点 /2就好
回复 支持 反对

使用道具 举报

hwu2498 发表于 2017-1-20 05:10:40 | 显示全部楼层
这道题leetcode上有吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-3-25 18:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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