谷狗新鲜店面

dengzeyu147 发表于 2018-11-29 04:14
请问这样做对吗
**** 本内容被作者隐藏 ****

你这样感觉不是 copy同一个修改后的B了吧？

betterztt 发表于 2019-1-4 09:00
你这样感觉不是 copy同一个修改后的B了吧？

那你修改一下来看看？我觉得我是对的。请指教

zzwcsong 发表于 2018-12-13 12:19
请问楼主，我下面的这几个test case是对的吗？

[mw_shl_code=java,true]

第一个错了："baba"可以由"cab"组成
第三个也错了：应该是2

如果我理解没错的话，每次可以删掉char后形成的subsequence可以不一样？
比如楼主的例子:
BABA 和 CAB
BABA = B(删去CA) + AB(删去C)+ A(删去CB)
所以一共三次？
怎么感觉这样会很复杂呢？
请指教我的理解是否正确

yliu2008 发表于 2018-12-22 07:31
1. Naive : O(mn)
2. optimized: O((m+n)*logm)
3. Further optimized: O(n+m^2)

老铁问下你第三个方法大概是什么？还能预处理m后优化到O(n)?

dertas1993 发表于 2019-1-16 11:28
老铁问下你第三个方法大概是什么？还能预处理m后优化到O(n)?

先build 一个lookup table，m*m size - 表示当前处于i位置，下一个要找j字母，需要走到哪一个位置, 如果这个值小于i当然就要用一个新的string了
然后遍历一次n

yliu2008 发表于 2019-1-16 11:43
先build 一个lookup table，m*m size - 表示当前处于i位置，下一个要找j字母，需要走到哪一个位置, 如果 ...

好思路，谢谢！