a*********0 发帖数: 2727 | 1 两个string判断是否可以match by insert/delete/replace one char of any one of
string。要求一遍扫描 |
a*********0 发帖数: 2727 | |
h*********o 发帖数: 230 | 3 跟前几天fb那个面镜一样吧。扫一遍就可以了吧
of
【在 a*********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 两个string判断是否可以match by insert/delete/replace one char of any one of : string。要求一遍扫描
|
b*********s 发帖数: 115 | 4 应该是可以的
因为只用考虑最多只有一个字符不同的情况
def match(s1, s2):
l1 = len(s1)
l2 = len(s2)
if abs(l1 - l2) > 1:
return False
if l2 < l1:
s1, s2 = s2, s1
l1, l2 = l2, l1
# replace
if l1 == l2:
count = 0
for c1, c2 in zip(s1, s2):
if c1 != c2:
count += 1
return count <= 1
# insert
else:
i = j = 0
while i < l1 and s1[i] == s2[j]:
i += 1
j += 1
j += 1
while i < l1 and s1[i] == s2[j]:
i += 1
j += 1
return i == l1 |
f*****t 发帖数: 13 | 5 这个题应该说“要求O(n)”。
of
【在 a*********0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 两个string判断是否可以match by insert/delete/replace one char of any one of : string。要求一遍扫描
|
S********e 发帖数: 74 | 6 scan from both left and right sides of the two strings, then see how many
different chars until left < right? |
m******n 发帖数: 187 | 7 用了len就不是一次了。
应该设3个flag。遇到第一个不相同的字符按照下一个字符分3种情况设好flag继续向前。
其实不可能3种可能同时出现,最多2种。
比如as vs. ss就是删除和取代两种情况都可能,as vs. sa就是删除和插入都可能。
【在 b*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是可以的 : 因为只用考虑最多只有一个字符不同的情况 : def match(s1, s2): : l1 = len(s1) : l2 = len(s2) : if abs(l1 - l2) > 1: : return False : if l2 < l1: : s1, s2 = s2, s1 : l1, l2 = l2, l1
|
u*****o 发帖数: 1224 | |
b*********s 发帖数: 115 | 9 string 的 len 是 O(1) 操作,不用扫
http://stackoverflow.com/questions/1115313/cost-of-len-function
前。
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用了len就不是一次了。 : 应该设3个flag。遇到第一个不相同的字符按照下一个字符分3种情况设好flag继续向前。 : 其实不可能3种可能同时出现,最多2种。 : 比如as vs. ss就是删除和取代两种情况都可能,as vs. sa就是删除和插入都可能。
|
m******n 发帖数: 187 | 10 谢谢,这等于是把一些info提前给了,猜想string在java和c++也是这样的。
【在 b*********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : string 的 len 是 O(1) 操作,不用扫 : http://stackoverflow.com/questions/1115313/cost-of-len-function : : 前。
|
J***o 发帖数: 553 | 11 c++的string虽然大部分实现是O(1),但标准里没强制要求。这题如果可以比较string
长度就简单了,不妨考虑一下输入是char*的情况。
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢,这等于是把一些info提前给了,猜想string在java和c++也是这样的。
|
b********r 发帖数: 620 | 12 how do as and sa meet the requirement? looks like we can only delete/insert/
replace one char in one of arrays?
前。
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用了len就不是一次了。 : 应该设3个flag。遇到第一个不相同的字符按照下一个字符分3种情况设好flag继续向前。 : 其实不可能3种可能同时出现,最多2种。 : 比如as vs. ss就是删除和取代两种情况都可能,as vs. sa就是删除和插入都可能。
|