作者RockLee (Now of all times)
看板Prob_Solve
标题[问题] Google Interview Question (1)
时间Mon Feb 11 12:39:17 2013
原始网址:
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)
用 Dynamic Programming 应该可在 O(n^2) 的时间内解决
但要在 O(n) 的时间内解决就想不出来了 Orz...
CareerCup 上的讨论看来都无法在 O(n) 的时间内正确的解决
不知道板上有没有人有什麽 idea?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.252.71.8
1F：推 atoi:是不是类似两个已排序的阵列要合并成一个排序好的阵列那样跑? 02/11 13:07
2F：→ atoi:ㄟ好像不太正确，歹势!! 02/11 13:13
3F：→ tkcn:↑不行，当 A, B, C 都是同个字元开头时，会不知该消耗哪个 02/11 13:15
4F：→ tjjh89017:用regex去跑(误 02/11 13:46
5F：→ bleed1979:CareerCup在那啊？我想看一下别人的讨论。 02/11 14:23
6F：→ RockLee:↑就我附的网址 02/11 14:39
7F：推 yoco315:无论如何只能想到 n^2 orz 02/16 13:09