Alien dictionary 及followup解题报告

最近在准备面试，打算写一些结题报告。大家多捧场。第一帖是alien dictionary 以及它的followup: get all solutions。这个follow up我没有写成alien dictionary，而是直接用了UVA 872的代码，但是原理一样，题目也极其类似，大家稍微变通一下就好。放在我的medium上：
https://medium.com/@wangfengfight/leetcode-269-alien-dictionary-and-followups-77c0390629da

楼主 这题我也深入研究过. follow up是典型的backtrack. 但是这里backtrack和别的lc题不一样

当前set里面存的是同等级的chars, 而咱们要for循环的也是这个set, 如果一般写法 就会造成concurrent modification的错

一个小技巧是 if 默认字母属于集合a到z.  我们循环a到z 看是否在set里面, 是的话就作为当前char 然后继续dfs.

楼主你的做法是copy 但是copy的cost太大.

你是copy下来当前set 然后循环  代价过大哈.

zhangzitong001 发表于 2019-3-10 12:29
楼主 这题我也深入研究过. follow up是典型的backtrack. 但是这里backtrack和别的lc题不一样

当前set里面 ...

谢谢赐教哈

zhangzitong001 发表于 2019-3-10 12:29
楼主 这题我也深入研究过. follow up是典型的backtrack. 但是这里backtrack和别的lc题不一样

当前set里面 ...

你好，我刚才又看了下，我觉得我的做法其实和你的建议并没有区别的，我的那个dict就是所有字母的数组，这个数组是一直传饮用的，每次loop over每个字母找indegree = 0，用完的标记成-1。实际上就是把原来BFS里的set拆成了每次26次的检查。

补充内容 (2019-3-10 13:09):
传引用...

wangfengfight1 发表于 2019/03/10 13:08:42


你好，我刚才又看了下，我觉得我的做法其实和你的建议并没有区别的，我的那个dict就是所有字母的数组，这个数组是一直传饮用的，每次loop over每个字母找indegree = 0，用完的标记成-...

ok.  你这是dfs版本的topo是吗.   我写的是原先题目bfs 进行topo的基础上, 对于当前indegree都为0的 char set 我选择其中一个 从set中删除 然后更新所有相邻的indegrees, 继续向下 然后backtrack.

zhangzitong001 发表于 2019-3-10 13:46
ok.  你这是dfs版本的topo是吗.   我写的是原先题目bfs 进行topo的基础上, 对于当前indegree都为0的 char ...

不是，我也是用BFS的topo，不过不使用set记录当前的零节点，而是每次检查每个字母，看看有没有0的，有就标记成-1加到结果里。我也看到你发的那个帖子，我觉得这题没法DP，而且应该是个可以规约到Hamilton path的NP问题...

wangfengfight1 发表于 2019/03/10 13:50:03


不是，我也是用BFS的topo，不过不使用set记录当前的零节点，而是每次检查每个字母，看看有没有0的，有就标记成-1加到结果里。我也看到你发的那个帖子，我觉得这题没法DP，而且应该是个可以规约到...

我那题不是这个题目呀 ... 你每次检查的操作我觉得不如加入到set里面.  如果你感兴趣我可以贴一下我的代码方便交流. 你可以看看我代码逻辑