x*******e 发帖数: 84 | 1 这个题解法是不是就是判断edit distance是否为1?还是有更好方法? |
D****3 发帖数: 611 | |
x*******e 发帖数: 84 | 3 具体什么好方法啊?
【在 D****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个不是直接遍历一遍就好了么
|
m*********a 发帖数: 3299 | 4 我就想到Dynamic programming
【在 x*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 具体什么好方法啊?
|
l*****a 发帖数: 14598 | 5 dp过时了,没人考
【在 m*********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我就想到Dynamic programming
|
l*****a 发帖数: 14598 | 6 你是分两个串长度相同/长度差一分别考虑
还是合在一起遍历一遍?
【在 D****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个不是直接遍历一遍就好了么
|
A*****i 发帖数: 3587 | 7 草……老子还没掌握呢就过时了
唉,还好没掌握
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : dp过时了,没人考
|
j**********3 发帖数: 3211 | |
a*******e 发帖数: 455 | 9 猜的,
同时扫两个数组, 当遇到第一个不match的, 之后剩下的就该都match了, O(n) |
s**x 发帖数: 7506 | 10 Scan until we reach the end or there is a mismatch, say aX mismatch bY,
Return true if one of the following is true:
1). X == Y
2) X == bY
3). aX == Y
code one for loop, probably 3 lines, finish in probably 3 minutes. |
w****r 发帖数: 15252 | 11 同喜,DP不就是recursive加个memory
【在 A*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 草……老子还没掌握呢就过时了 : 唉,还好没掌握
|
v***o 发帖数: 287 | 12 如果是substring 的 one edit distance?
ex. whati -> ti, wka, ayi ....
【在 x*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题解法是不是就是判断edit distance是否为1?还是有更好方法?
|
b****r 发帖数: 1 | |
p****6 发帖数: 724 | 14 public static boolean oneEditApart(String a, String b) {
String small = a.length() > b.length() ? b : a;
String large = a.length() > b.length() ? a : b;
int operation = 0;
//case 1, two word's length differ by more than one
if(large.length() - small.length() > 1) return false;
//case 2, length is equal, check every char one by one
else if(large.length() == small.length()){
int i = 0;
while(i < small.length()){
if(small.charAt(i) != large.charAt(i) && ++operation > 1)
return false;
i++;
}
//case 3, two word's length differ by one, only one differ allow
}else{
int i = 0;
while(i < small.length()){
if(small.charAt(i) != large.charAt(i+operation)){
if(++operation > 1)
return false;
}else i++;
}
}
return true;
} |