作者eight0 (一直到今天)
站內Prob_Solve
標題Re: [問題] Google Interview Question (1)
時間Tue May 14 00:06:45 2013
※ 引述《RockLee (Now of all times)》之銘言：
原始網址:
http://www.careercup.com/question?id=14539805
題目:
Three strings say A, B, C are given to you.
Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)
--
看了前面前輩的做法，困難點都是在遇到重覆字元時的問題。
下面來解釋為何抓前2個字元就能解決。
1. A[0] != B[0]
當A[0]!=B[0]時，必定A[0]==C[0] or B[0]==C[0]
選擇正確的字元取出即可
Ex: a??? b??? b?a????? --> a??? ??? ?a?????
2. A[0] == B[0] == A[1] == B[1]
這時的字串長的像這樣
aa?? aa?? aa?a?a??
這時不管取出任意一方的字元都沒有影響
a?? aa?? a?a?a??
aa?? a?? a?a?a??
3. A[0] == B[0] == A[1] ==
C[1] != B[1]
如下
aa?? ab?? aaba?a??
取出A和取出B的決定性差異在於
取出後有沒有解
取出A
a?? ab?? aba?a??
取出B
aa?? b?? aba?a??
注意到取出B的話
B[0] 會改變且 A[0],C[0]不變
這個情況
可能會導致無解，所以選擇取出A，取出
A的同時我們能保證
現階段有解
另一種情況的字串
aa?? ab?? aab?a??? --> a?? ab?? ab?a???
4. A[0] == B[0] == B[1] == C[1] != A[1]
這個情況剛好是3.的相反，所以直接取出B。
大致上是這樣，希望沒錯OwQ
--
(*￣▽￣)/‧★*"`'*-.,_,.-*'`"*-.,_☆,.-*`
http://i.imgur.com/oAd97.png
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.204.67
1F：推 suhorng:欸特推一個 05/14 00:09
2F：→ atoi:第2點有沒有可能是 aa?? aa?? aa??aa??阿 05/14 00:24
3F：→ jhchou:我用你上一篇的連結測aaax aaay aaaayaax 結果是false 05/14 00:24
4F：→ eight0:! 樓上是對的 第2點的處理方法不正確 05/14 00:28
5F：→ Leon:你只有用 2-step Dynamic programming, string 一長會失敗 05/14 01:55
7F：→ eight0:晚上再來討論2.的狀況 05/14 13:40