C***U 发帖数: 2406 | 1 给定两个strings x和y,以及一个值t,需要判断这两个strings的edit distance是否大
于t
O(t*n)时间 O(t)空间算法 |
C***U 发帖数: 2406 | 2 int checkEditDistanceFast(const char *pattern, int pLen, const char* text,
int tLen, int editD) {
//if the edit distance is larger than the length difference, then return
false
if(editD < abs(pLen - tLen)) {
return MAX;
}
else {
//compute the number of diagonals requiring consideration
int p = (editD - abs(pLen - tLen)) / 2;
int t = tLen >= pLen ? -p : tLen - pLen - p;
int s = t + 1;
int len = abs(pLen - tLen) + 2 * p + 1;
//initialize the row
int *row = new int[len];
for(int k = 0; k < len; k++) {
row[k] = ((k + t < 0 || k + t > tLen) ? MAX : k + t);
}
//compute row by row
for(int i = 1; i <= pLen; i++) {
bool flag = true;
for(int j = 0; j < len; j++) {
if(j + s < 0 || j + s > tLen) {
row[j] = MAX;
}
else if(j + s == 0) {
int l, u;
l = j - 1 < 0 ? MAX : (row[j - 1] + 1);
u = j + 1 >= len ? MAX : (row[j + 1] + 1);
row[j] = u < l ? u : l;
}
else {
int d, l, u;
d = row[j] + (pattern[i - 1] == text[j + s - 1] ? 0 : 1);
l = j - 1 < 0 ? MAX : (row[j - 1] + 1);
u = j + 1 >= len ? MAX : (row[j + 1] + 1);
row[j] = d < l ? d : l;
row[j] = row[j] < u ? row[j] : u;
}
flag = flag && (row[j] > editD);
}
if(flag)
return MAX;
s++;
}
//get the edit distance
int result = row[abs(pLen - tLen) + 2 * p + t];
delete[] row;
//check edit distance
return result <= editD ? result : MAX;
}
}
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给定两个strings x和y,以及一个值t,需要判断这两个strings的edit distance是否大 : 于t : O(t*n)时间 O(t)空间算法
|
B*******1 发帖数: 2454 | 3 原题在哪里啊?
看你的这个描述看得不是很清晰。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给定两个strings x和y,以及一个值t,需要判断这两个strings的edit distance是否大 : 于t : O(t*n)时间 O(t)空间算法
|
C***U 发帖数: 2406 | 4 给你两个string x和y,我们可以算他们的edit distance。这个leetcode上面好像有吧
? 用DP就算出来他们的edit distance是多少。但是这个算法是O(n^2)的。现在我不用
你算具体的edit distance。我告诉你一个正整数t。让你判断这两个edit distance是
不是小于等于t。我们当然可以用DP算法来做算出edit distance是多少。但是现在有更
好的算法,当t小的时候。
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原题在哪里啊? : 看你的这个描述看得不是很清晰。
|
f*****e 发帖数: 2992 | 5 仍然用DP做:
好像是一个n by n的表,不用每个entry都算出来,只算t对角阵(t-diagnal),因为每
个元素只能用到另一个数组元素里面的2t个元素,比如A数组的长度为L1,B数组的长度
为L2,则A数组的ith元素x,只能用到B数组的[L2-(L1-i+1)-t,L2-(L1-i+1)+t]th元素。
如果超过这个范围,他右边的edit distance铁定超过t了。
所以...
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给你两个string x和y,我们可以算他们的edit distance。这个leetcode上面好像有吧 : ? 用DP就算出来他们的edit distance是多少。但是这个算法是O(n^2)的。现在我不用 : 你算具体的edit distance。我告诉你一个正整数t。让你判断这两个edit distance是 : 不是小于等于t。我们当然可以用DP算法来做算出edit distance是多少。但是现在有更 : 好的算法,当t小的时候。
|
C***U 发帖数: 2406 | 6 对
我的code基本上就是这个意思
你帮我看看有什么地方可以优化的
:)
为每
素。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 仍然用DP做: : 好像是一个n by n的表,不用每个entry都算出来,只算t对角阵(t-diagnal),因为每 : 个元素只能用到另一个数组元素里面的2t个元素,比如A数组的长度为L1,B数组的长度 : 为L2,则A数组的ith元素x,只能用到B数组的[L2-(L1-i+1)-t,L2-(L1-i+1)+t]th元素。 : 如果超过这个范围,他右边的edit distance铁定超过t了。 : 所以...
|
c********t 发帖数: 5706 | 7 你还在做题啊?你是已经接受G offer了吗?还是要面F?
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给定两个strings x和y,以及一个值t,需要判断这两个strings的edit distance是否大 : 于t : O(t*n)时间 O(t)空间算法
|
C***U 发帖数: 2406 | 8 接了offer了。不过f会给我面试就是了
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你还在做题啊?你是已经接受G offer了吗?还是要面F?
|
c********t 发帖数: 5706 | 9 加油,等待你的面经!
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 接了offer了。不过f会给我面试就是了
|