一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1014|回复: 10
收起左侧

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 | 显示全部楼层
小A要当码农 发表于 2016-10-14 05:02
这题不能直接DP么。。。?
. 鍥磋鎴戜滑@1point 3 acres
直接DP的话 要怎么做呀?
回复 支持 1 反对 0

使用道具 举报

ericlee27 发表于 2016-10-13 08:20:23 | 显示全部楼层
这道题你把这个字符串翻转过来做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);. visit 1point3acres.com for more.
  4.         String b = sb.reverse().toString();
  5.         System.out.print(minDistance(a, b));
  6.     }

  7.     public static int minDistance(String word1, String word2) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.         int length1 = word1.length();
  9.         int length2 = word2.length(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.         if (length1 == 0 || length2 == 0) return Math.max(length1, length2);
  11.         int[][] dp = new int[length1 + 1][length2 + 1];
  12.         dp[0][0] = 0;
  13.         for (int i = 1; i <= length1; ++i) {
  14.             dp[i][0] = i;
  15.         }
  16.         for (int j = 1; j <= length2; ++j) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  17.             dp[0][j] = j;
  18.         }

  19.         // DP
  20.         for (int i = 1; i <= length1; ++i) {
  21.             for(int j = 1; j <= length2; ++j) {
  22.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.                     dp[i][j] = dp[i - 1][j - 1];
  24.                 } else {
  25.                     dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
  26.                 }
  27.             }
  28.         }
  29.         int minEdit = Integer.MAX_VALUE;
  30.         int x = 0;
  31.         int y = word1.length();
  32.         while (x <= length2 && y >= 0) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.             int diagnoal = dp[y][x];
  34.             int top = y >= 1 ? dp[y - 1][x] : Integer.MAX_VALUE; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  35.             int bottom = y < length1 ? dp[y + 1][x] : Integer.MAX_VALUE;
  36.             int smallest = Math.min(diagnoal, Math.min(top, bottom));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  37.             minEdit = Math.min(smallest, minEdit);
  38.             x++;
  39.             y--;
  40.         }
  41.         return minEdit;
  42.     }
复制代码
回复 支持 反对

使用道具 举报

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

这题不能直接DP么。。。?
回复 支持 反对

使用道具 举报

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 沿着从左下到右上的对角线找,如果是偶数长度,只找对角线, ...
. 1point3acres.com/bbs
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 发表于 6 天前 | 显示全部楼层
ericlee27 发表于 2016-10-13 08:20
这道题你把这个字符串翻转过来做EDIT DISTANCE 沿着从左下到右上的对角线找,如果是偶数长度,只找对角线, ...

感谢分享code。能解释一下逻辑吗?
我在overstack上面看到一个算法,觉得挺对的。
http://stackoverflow.com/questio ... removals-of-charact
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 发表于 5 天前 | 显示全部楼层

初始化的地方明显不对

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

使用道具 举报

kin332026 发表于 4 天前 | 显示全部楼层
大家看下,可以这样吗?

  1. public int minEdit(String s) {
  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) {
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.                 }
  13.                 l++;
  14.                 r++;
  15.             }
  16.         }. 1point3acres.com/bbs
  17.         return dp[0][length - 1];
  18.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 12:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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