作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] Google Interview Question (1)
时间Wed Feb 13 16:27:48 2013
※ 引述《atoi (atoi)》之铭言：
: 我的想法是这样不知道对不对
: 分别用A和B字串去扫C字串
: 就是例如 A="acd"，B="bac"，C="bacacd"
: 用A去扫 "bacacd"，找第一个match就行
: ^^ ^
: 再用B扫 "bacacd"，一样找第一个match就行
: ^^^
: 然後两者重复的地方是ac
: 可以搬到没被match的地方，也就是"bacacd"里面右边的ac
: 那就是interleave的
: 否则就不是
: ㄟ不知道这样行不行，可能没那麽简单，不好意思
这可以 run, 但是应该是 O(N^2).
你去试试看这个例子就知道了.
A = 'aa', B = 'abaab', C = 'aabaaab'
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 142.136.127.112
1F：→ atoi:A和B各扫一次之後，再扫一次，过程中把重复的丢到queue里， 02/13 19:13
2F：→ atoi:遇到还没match的就从queue里检查，且pop掉，整个跑完如果是 02/13 19:14
3F：→ atoi:interleave那就刚好每个字元对应一次，不知道这样有没有弄错 02/13 19:15
4F：→ atoi:这样三次都是O(N) 02/13 19:18
5F：→ Leon:then it will go back to my method, or Dynamic Prog 02/14 01:41