snapchat新鲜昂赛跪经

keytion · 2016-10-27 01:07:51

一个trie,每个节点两个状态， isPrefix, isWord;
再加个遍历输出所有prefix,或者word应该就可以了吧。。

clxy2008 · 2016-10-27 03:16:59

求问楼主，青蛙跳河二维怎么跳，我只能想到用memorization了，dp[][][][] 前两维是上一个点坐标，后两维是x跳了多少，y跳了多少才跳到这个点的

xiaoyehhuang23 · 2016-10-27 03:57:16

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

xiaoyehhuang23 · 2016-10-27 03:58:09

keytion 发表于 2016-10-27 01:07
一个trie,每个节点两个状态， isPrefix, isWord;
再加个遍历输出所有prefix,或者word应该就可以了吧。。

你这么做和用两个trie并没有本质差别吧？空间复杂度应该是一样的吧？但是还要加上判断什么的反而更复杂了？

keytion · 2016-10-27 04:06:04

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

clxy2008 · 2016-10-27 04:06:28

这道题本质就是一个bfs，我在lc上用bfs是过了的，最差就是这个青蛙一直一步一步跳，对于每一个点，这个青蛙有可能是从前面的任何一个点跳过来的，所以我觉得是 n^2

linweihua0 · 2016-10-27 07:59:28

青蛙跳这题肯定不是polynomial 比较loose的bound应该是O(3^n) 每个Stone triple possible steps

keytion · 2016-10-27 08:26:27

1维青蛙跳，DP的话：
如果不能往后跳，那么i节点可能的步数最多是O(i^0.5);
所以在每个节点，需要check O(i^0.5) 次，假设用hashset check是O(1);
那么总共的cost 差不多 O(n^1.5);

xiaoyehhuang23 · 2016-10-27 08:33:35

keytion 发表于 2016-10-27 08:26
1维青蛙跳，DP的话：
如果不能往后跳，那么i节点可能的步数最多是O(i^0.5);
所以在每个节点，需要check O ...

对我和你的复杂度算的是一样的。。。你上面那个trie说的也很有道理，厉害啊

xiaoyehhuang23 · 2016-10-27 08:42:18

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式