※ 引述《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? 这是一个很快的想法, 我不知道对不对, 反正大家讨论一下. You can put two flags on string A and B, then scan every character in C. for example, the first step, it will be, A = a | bcd and B = | xyz. then it's not hard to see if the flag of A,B move to the end. One problem is the one it points out in the webpage. if A = 'ca', B = 'cb' , C = 'cacb' or 'cbca' should be both true. So, when you scan the character, you need to put an additional index to handle the duplicate character. In this situation, C = 'cacb', when you do the scan of the fist char A = c | a and B = c | b, but both has index = 1. In the next step, you scan second char, which is a, Now, A = 'c a |' and you reset the index of A into 0. at the same time you push the flag of B back with 1. So B = '| c b'. This should be running in a linear time? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 142.136.127.217