x*******e
发帖数: 84 | 1 这个题解法是不是就是判断edit distance是否为1？还是有更好方法？ |
D****3
发帖数: 611 | |
x*******e
发帖数: 84 | 3 具体什么好方法啊？
【在 D****3 的大作中提到】
: 这个不是直接遍历一遍就好了么
|
m*********a
发帖数: 3299 | 4 我就想到Dynamic programming
【在 x*******e 的大作中提到】
: 具体什么好方法啊？
|
l*****a
发帖数: 14598 | 5 dp过时了，没人考
【在 m*********a 的大作中提到】
: 我就想到Dynamic programming
|
l*****a
发帖数: 14598 | 6 你是分两个串长度相同／长度差一分别考虑
还是合在一起遍历一遍？
【在 D****3 的大作中提到】
: 这个不是直接遍历一遍就好了么
|
A*****i
发帖数: 3587 | 7 草……老子还没掌握呢就过时了
唉，还好没掌握
【在 l*****a 的大作中提到】
: 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 的大作中提到】
: 草……老子还没掌握呢就过时了
: 唉，还好没掌握
|
v***o
发帖数: 287 | 12 如果是substring 的 one edit distance?
ex. whati -> ti, wka, ayi ....
【在 x*******e 的大作中提到】
: 这个题解法是不是就是判断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;
} |
