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

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

题目：
给出一个有向图的结构
START --> a --> b --> c --> 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,题目都没说吧

class GraphNode:
        def __init__(self, val):
                self.val = val
                self.neighbors = []


def is_valid(s, graph_start):
       
        if graph_start is None:
                return False

        # Suppose the start and end nodes in the graph have the value S and E
        s = 'S' + s + 'E'

        q = collections.deque([graph_start])

        for i in range(len(s)):
                matched = False
                qsize = len(q)

                for k in range(qsize):
                       
                        front = q.popleft()
                        curr_matched = (front.val == s[i])
                        matched = matched or curr_matched
                       
                        if curr_matched:
                                for neighbor in front.neighbors:
                                        q.append(neighbor)
                if not matched:
                        return False

        return True

bool checkUtil(string str, int pos, GraphNode *cur) {
  if (pos == str.length())
    return cur->isEnd;


  char curCh = str[pos];

  for (auto s : cur->succs) {
        if (s->ch == curCh) {
            if (checkUtil(str, pos+1, s))
                return true;
        }
  }
  return false;

}

bool checkWord(string str) {
  if (str.empty())
    return false;

  return checkUtil(str, 0, root);
}

main() {

    root = new GraphNode();

    GraphNode *an = new GraphNode('a');
    root->succs.push_back(an);

    GraphNode *bn = new GraphNode('b');
    an->succs.push_back(bn);

    GraphNode *a2n = new GraphNode('a');
    bn->succs.push_back(a2n);
    bn->succs.push_back(an);

    a2n->isEnd = true;

    printf("%s\n", checkWord("ababa") ? "true" : "false");
    printf("%s\n", checkWord("aba") ? "true" : "false");
    printf("%s\n", checkWord("ab") ? "true" : "false");
}

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

这就是个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