【求助】虚心请教经典题目摩斯密码思路解法

dtccx 发表于 2018-4-4 18:47
摸摸，注意身体，身体是革命的本钱

谢谢关心，大家互勉

麻倉枼 发表于 2018-4-5 07:41
已经给了，大神觉得够不够？

谢谢大米~
大神不敢当，我也只是漫漫刷题求职路上的一员。。

同祝早日康复~

foreveriii3 发表于 2018-4-4 19:47
谢谢大米~
大神不敢当，我也只是漫漫刷题求职路上的一员。。

谢谢哈，大家共勉

感觉应该可以用里扣 咬撕零的方法。

狗家对DFS + memo这类题真是热爱。。

麻倉枼 发表于 2018-4-5 03:09
谢谢，好像解决了，很漂亮的解法！

想问下楼主如果用backtracking & memorization set的话，时间和空间复杂度分别应该是多少？

julieusc 发表于 2019-1-27 15:17
想问下楼主如果用backtracking & memorization set的话，时间和空间复杂度分别应该是多少？

我来说说我的想法。

加上memorization，DFS被叫的次数会变为 O(N^2)

但HashMap里的总共的方案，仍然会有O（2^N）个。最坏情况是
1, 1 方案
2, 2 方案
3, 4 方案
4, 8 方案
...
方案里面的每个String都会有长度N。

因此我认为总共的空间复杂度O（2^N），时间复杂度是O(N^2 + N*2^N)

补充内容 (2019-1-28 05:55):
空间复杂度漏了应为O(N*2^N)