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 的大作中提到】
: 给定两个strings x和y,以及一个值t，需要判断这两个strings的edit distance是否大
: 于t
: O(t*n)时间 O(t)空间算法
|
B*******1
发帖数: 2454 | 3 原题在哪里啊？
看你的这个描述看得不是很清晰。
【在 C***U 的大作中提到】
: 给定两个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 的大作中提到】
: 原题在哪里啊？
: 看你的这个描述看得不是很清晰。
|
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 的大作中提到】
: 给你两个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 的大作中提到】
: 仍然用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 的大作中提到】
: 给定两个strings x和y,以及一个值t，需要判断这两个strings的edit distance是否大
: 于t
: O(t*n)时间 O(t)空间算法
|
C***U
发帖数: 2406 | 8 接了offer了。不过f会给我面试就是了
【在 c********t 的大作中提到】
: 你还在做题啊？你是已经接受G offer了吗？还是要面F?
|
c********t
发帖数: 5706 | 9 加油，等待你的面经！
【在 C***U 的大作中提到】
: 接了offer了。不过f会给我面试就是了
|
