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

[eight0 (一直到今天)]

※ 引述《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
推 suhorng:欸特推一個
→ atoi:第2點有沒有可能是 aa?? aa?? aa??aa??阿
→ jhchou:我用你上一篇的連結測aaax aaay aaaayaax 結果是false
→ eight0:! 樓上是對的 第2點的處理方法不正確
→ Leon:你只有用 2-step Dynamic programming, string 一長會失敗
→ eight0:http://jsfiddle.net/h73Fr/8/ 這樣是能跑了 但有點不確定
→ eight0:晚上再來討論2.的狀況