Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者eight0 (一直到今天)時間11年前 (2013/05/14 00:06)推噓1(1推 0噓 6→)留言7則, 5人參與討論串15/16 (看更多)
※ 引述《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
推
05/14 00:09, , 1F
05/14 00:09, 1F
→
05/14 00:24, , 2F
05/14 00:24, 2F
→
05/14 00:24, , 3F
05/14 00:24, 3F
→
05/14 00:28, , 4F
05/14 00:28, 4F
→
05/14 01:55, , 5F
05/14 01:55, 5F
→
05/14 13:39, , 6F
05/14 13:39, 6F
→
05/14 13:40, , 7F
05/14 13:40, 7F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 15 之 16 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
