SNAPCHAT电面挂经

freemail165 发表于 2016-10-10 06:18
你说的很简单，但是第二部你怎么做？
你得找到所有可能的key组合，能生成第一个输入的string

用dfs就可以得到所有的dict内的string的组合呀，然后每得到一个组合就sort一下，然后key已经存在了就把组合append到后面，不存在就放一个新的key进去。做这些的时候不考虑第一个输入的string，把这些做完之后每调用一次API（获得一个新的string）就去key value pair里去找，哪里有什么问题吗？

todayand 发表于 2016-9-19 19:41
因为顺序不重要，所以可以将INPUT STRING ARRAY 2里的string先sort，建个hashmap存sorted string对应原stri ...

请问建完树以后要如何dfs找到所有pairs？如果ga，gat都是一个word，找到ga以后该如何继续dfs？
g
|
a
|
t

类似coin change

这题是不是可以用subset思想去做。 array1只需要每个char的count, 之后求出array2所有的subset, 计算每个subset的char count, 最后把count相等的subset加到结果中。

我是面的同一题。Trie +Dfs +backtrack跑出来了

弱视个体 发表于 2016-11-4 06:41
我是面的同一题。Trie +Dfs +backtrack跑出来了

可否说一下你写的思路，还是不太明白如何使用trie在这题。例如arr1 :["a", "gaat"], arr2: ["ga", "gat"].
对arr2建trie
g
|
a
|
t

这里如何找arr1 呢

补充内容 (2016-11-7 05:33):
写错, arr1：["a", "gagt"]

tzthink 发表于 2016-11-7 05:32
可否说一下你写的思路，还是不太明白如何使用trie在这题。例如arr1 :["a", "gaat"], arr2: ["ga", "gat"] ...

你理解错了。arr1 是char数组。用一个Map存频率，一个一个取，直到没有char。路上碰到string就加入结果集。可以用一个set去重。

弱视个体 发表于 2016-11-4 06:41
我是面的同一题。Trie +Dfs +backtrack跑出来了

Trie是根据array2建的吗？糊涂了