作者DJWS (...)
看板Prob_Solve
标题Re: [问题] Google Interview Question (1)
时间Wed Feb 13 11:20:14 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?
抱歉又来灌水了～
比如说 A 中的 'a' 和 'd' 交换位置，C 中的 'a' 和 'd' 交换位置。
那麽结果应该不会改变吧？
也许可以运用 selection sort 的概念，
用两两交换的方式，把 A 和 B 排序好，
每当 A (和B) 的两个字元交换位置，
就想办法从 C 当中找到对应的两个字元，跟着 A (和B) 一起交换位置。
最後 A 和 B 都排序好之後，
如果 C 也是排序好的，就一定是 interleaved 了，反之则不是。
为了达到 O(N)，
实作的时候就先扫描一次 A 和 B 和 C，
用 bucket sort 的概念，把每个字母出现的位置预先求出来，
也许就比较容易交换了。
听起来好像很有道理，
但是我根本就不确定这样对不对，
所以仅供参考... XD
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 36.225.128.213
※ 编辑: DJWS 来自: 36.225.128.213 (02/13 11:25)
1F：→ eieio:前面推文就有isnoneval:A=xy, B=xxxy, C=xxyxxy? 02/13 12:22
2F：→ DJWS:感谢楼上举的例子～ 02/14 19:31
3F：→ DJWS:那麽能不能A跟B交换字元呢？比如说A[0]和B[0]交换... 02/14 19:32
※ 编辑: DJWS 来自: 36.225.130.142 (02/14 20:04)