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

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

楼主~有环的话有关系吗？不是说给定字符串的长度是确定的话，即使有环也不会进入死循环呀。还有既然是有向图，那么图里有重复字符又怎么样呢？

已经收到据电了吗？没有收到据电的话都是还有希望的

ryuichist 发表于 2018-2-13 04:32
比如这种情况

START -> a  a  a -> END

还是不太明白为啥有环的话Trie就不行了呢？在Trie上进行BFS感觉也可以啊？LZ能否再解释一下，谢谢

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

为什么DFS不行呢？能否详细的解释下？

luogaoqi 发表于 2018-2-13 05:57
这些A一定是同一个node吗 还是可以是3个不同的node with same value a,是否允许走环， 是否允许duplicate v ...

是三个不同的node，可以看成a1, a2, a3

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

exthrash 发表于 2018-2-26 04:46
class GraphNode:
        def __init__(self, val):
                self.val = val

你的解法有点input string driven 的味道
所以我个人理解，如果从这个角度解这道题的话，是不是就天然的解决掉有环和有重复元素的情况。
因为最终返回true的条件是 i 能走完string，且最后以end结尾。
如果这个思路正确，那dfs+backtracking也是可以的

str = str + E
boolean dfs(String str, int index, GraphNode root) {
    if (root.isEnd() && index==str.length()) return true;
    for (int i=index; i<str.length; i++) {
        for (GraphNode child: root.children) {
            if (child.val==str.charAt(i)) {
                dfs(str, i+1; child);
            }
        }
    }
    return false;
}