毛主席说过一句话# PhotoGear - 摄影器材
g*y
1 楼
Edit： 好像不对，还是更复杂的情况。
想了一个O（n）的解法。请帮忙看一下对不对。
if A and B have no duplicate char: easy problem. just traverse C. increase A
's
index if A's char matches or increase B's index if B's char matches.
if A and B have duplicate chars, we assume A[i, j] == B[m, n].
when we traverse C and in the position where C[k] == A[i] == B[m], we have
two ways to go: increase A's index or increase B's index. in this kind of
situation, we will always select to increase A's index.
if we are lucky, A is the right way to go, we are good.
if we select a wrong way to go, which means we should have increased B's
index, but we increased A's index. we won't find it wrong before we
reaches A[j + 1]. assume A has gone through a_l elements since i and B has
go through b_l elements since m. at this time, we know we might have
selected a wrong way. therefore, we tried to swap a_l and b_l, i.e. A's
index is set to i + b_l and B's index is set to m + a_l, i.e. n + 1. and
redo the comparisons between B[n + 1] and the current char in C. if we got a
match, we continue to traverse C; otherwise return false.
A: abe
B: abd
C: abadbe
when C reaches C[3], i.e. d, A is at the position A[2] and B is at the
position B[1]. C[3] != A[2] != B[1]
we realize that we might have selected a wrong, we swap A's index increment
and B's index increment since the last A[i] == B[j]. in this example, i = j
= 0. so A's index is set to 1 and B's index is set to 2.
def is_interleaved(astr, bstr, cstr):
"""Given three strings, a, b and c, check if c is interleaved from a and
b.
For example: a = "abcd", b = "xyz", c = "axbyzcd" => True.
Give a O(n) algorithm"""
ai, bi, ci = 0, 0, 0
dup_al, dup_bl = 0, 0
while ci < len(cstr):
if ai == len(astr) and bi == len(bstr):
return False
if ai < len(astr) and cstr[ci] == astr[ai]:
if bi != len(bstr) and astr[ai] == bstr[bi]:
dup_al += 1
ai += 1
ci += 1
elif bi < len(bstr) and cstr[ci] == bstr[bi]:
if ai != len(astr) and bstr[bi] == astr[ai]:
dup_bl += 1
bi += 1
ci += 1
elif dup_al != 0 or dup_bl != 0:
ai = ai - dup_al + dup_bl
bi = bi - dup_bl + dup_al
dup_al, dup_bl = 0, 0
else:
return False;
return ai == len(astr) and bi == len(bstr)
想了一个O（n）的解法。请帮忙看一下对不对。
if A and B have no duplicate char: easy problem. just traverse C. increase A
's
index if A's char matches or increase B's index if B's char matches.
if A and B have duplicate chars, we assume A[i, j] == B[m, n].
when we traverse C and in the position where C[k] == A[i] == B[m], we have
two ways to go: increase A's index or increase B's index. in this kind of
situation, we will always select to increase A's index.
if we are lucky, A is the right way to go, we are good.
if we select a wrong way to go, which means we should have increased B's
index, but we increased A's index. we won't find it wrong before we
reaches A[j + 1]. assume A has gone through a_l elements since i and B has
go through b_l elements since m. at this time, we know we might have
selected a wrong way. therefore, we tried to swap a_l and b_l, i.e. A's
index is set to i + b_l and B's index is set to m + a_l, i.e. n + 1. and
redo the comparisons between B[n + 1] and the current char in C. if we got a
match, we continue to traverse C; otherwise return false.
A: abe
B: abd
C: abadbe
when C reaches C[3], i.e. d, A is at the position A[2] and B is at the
position B[1]. C[3] != A[2] != B[1]
we realize that we might have selected a wrong, we swap A's index increment
and B's index increment since the last A[i] == B[j]. in this example, i = j
= 0. so A's index is set to 1 and B's index is set to 2.
def is_interleaved(astr, bstr, cstr):
"""Given three strings, a, b and c, check if c is interleaved from a and
b.
For example: a = "abcd", b = "xyz", c = "axbyzcd" => True.
Give a O(n) algorithm"""
ai, bi, ci = 0, 0, 0
dup_al, dup_bl = 0, 0
while ci < len(cstr):
if ai == len(astr) and bi == len(bstr):
return False
if ai < len(astr) and cstr[ci] == astr[ai]:
if bi != len(bstr) and astr[ai] == bstr[bi]:
dup_al += 1
ai += 1
ci += 1
elif bi < len(bstr) and cstr[ci] == bstr[bi]:
if ai != len(astr) and bstr[bi] == astr[ai]:
dup_bl += 1
bi += 1
ci += 1
elif dup_al != 0 or dup_bl != 0:
ai = ai - dup_al + dup_bl
bi = bi - dup_bl + dup_al
dup_al, dup_bl = 0, 0
else:
return False;
return ai == len(astr) and bi == len(bstr)
