Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間11年前 (2013/02/13 11:20)推噓0(0推 0噓 3→)留言3則, 2人參與討論串5/16 (看更多)
※ 引述《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)
→
02/13 12:22, , 1F
02/13 12:22, 1F
→
02/14 19:31, , 2F
02/14 19:31, 2F
→
02/14 19:32, , 3F
02/14 19:32, 3F
※ 編輯: DJWS 來自: 36.225.130.142 (02/14 20:04)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 16 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
