Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者afafaf (你防水我怎麼丟@@)時間11年前 (2013/04/16 23:13)推噓0(0推 0噓 1→)留言1則, 1人參與討論串11/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?
int arr[26] = {0}, 代表a~z counter
把A, B的字母遇到則加, C的字母遇到則減,
最後check arr是否全0, O(n)吧
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.8.167
→
04/16 23:29, , 1F
04/16 23:29, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 11 之 16 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
