作者afafaf (你防水我怎麽丢@@)
看板Prob_Solve
标题Re: [问题] Google Interview Question (1)
时间Tue Apr 16 23:13:51 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)
: 用 Dynamic Programming 应该可在 O(n^2) 的时间内解决
: 但要在 O(n) 的时间内解决就想不出来了 Orz...
: CareerCup 上的讨论看来都无法在 O(n) 的时间内正确的解决
: 不知道板上有没有人有什麽 idea?
int arr[26] = {0}, 代表a~z counter
把A, B的字母遇到则加, C的字母遇到则减,
最後check arr是否全0, O(n)吧
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.42.8.167
1F：→ suhorng:顺序呢? A=ab, B=c, C=cba 04/16 23:29