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 的大作中提到】
: 两个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 的大作中提到】
: 两个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 的大作中提到】
: 应该是可以的
: 因为只用考虑最多只有一个字符不同的情况
: 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 的大作中提到】
: 用了len就不是一次了。
: 应该设3个flag。遇到第一个不相同的字符按照下一个字符分3种情况设好flag继续向前。
: 其实不可能3种可能同时出现，最多2种。
: 比如as vs. ss就是删除和取代两种情况都可能，as vs. sa就是删除和插入都可能。
|
m******n
发帖数: 187 | 10 谢谢，这等于是把一些info提前给了，猜想string在java和c++也是这样的。
【在 b*********s 的大作中提到】
: 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 的大作中提到】
: 谢谢，这等于是把一些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 的大作中提到】
: 用了len就不是一次了。
: 应该设3个flag。遇到第一个不相同的字符按照下一个字符分3种情况设好flag继续向前。
: 其实不可能3种可能同时出现，最多2种。
: 比如as vs. ss就是删除和取代两种情况都可能，as vs. sa就是删除和插入都可能。
|
