Re: [问题] Google Interview Question (1)

楼主: afafaf (bb)   2013-04-16 23:13:51
※ 引述《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)吧
作者: suhorng ( )   2013-04-16 23:29:00
顺序呢? A=ab, B=c, C=cba

Links booklink

Contact Us: admin [ a t ] ucptt.com