作者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