Re: [問題] Google Interview Question (1)

[Leon (Achilles)]

※ 引述《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
→ atoi:A和B各掃一次之後，再掃一次，過程中把重複的丟到queue裡，
→ atoi:遇到還沒match的就從queue裡檢查，且pop掉，整個跑完如果是
→ atoi:interleave那就剛好每個字元對應一次，不知道這樣有沒有弄錯
→ atoi:這樣三次都是O(N)
→ Leon:then it will go back to my method, or Dynamic Prog