※ 引述《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