狗狗电面2面面筋，跪，2018-02-05

狗狗电面2面，时间2月5日

题目：
给出一个有向图的结构
START --> a --> b --> c --> END

如果一个单词能够从start开始，在END结束，

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

做到第四问的时候时间差不多快到了
小哥说没问题，我知道你的思路了（事实证明有问题）

move on了，希望对其他同学有帮助

这些A一定是同一个node吗 还是可以是3个不同的node with same value a,是否允许走环， 是否允许duplicate value node,题目都没说吧

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

里面有重复字符是什么意思呢？

这就是个Trie吧…

用trie不行吗？ 为什么要用图呢？

devilnut 发表于 2018-2-12 23:40
这就是个Trie吧…

Trie 怎么解决环呢？

这应该是个 BFS 题。DFS 不能解决环，即使是用 visited set 判断。比如一个字符串在环上绕过两圈之后可以找到 End。可以用一个 Queue 记录所有当前合法的节点，同时维护一个每层的节点数的 var。如果新的 char 和 queue.poll() 一样，就把它的 nexts 们 offer 进 queue中。结束条件是 END 的时候找到 END。重复字符问题也可以解决。

weile77 发表于 2018-2-13 03:19
这应该是个 BFS 题。DFS 不能解决环，即使是用 visited set 判断。比如一个字符串在环上绕过两圈之后可以找 ...

是的，明显的BFS题目，主要是follow up

harveyaya 发表于 2018-2-13 01:12
Trie 怎么解决环呢？

Trie不行的，因为follow up有提到，有可能有环

ryuichist 发表于 2018-2-13 04:28
是的，明显的BFS题目，主要是follow up

比如这种情况

START -> a <--> a <--> a -> END