求Google高频题Trie的解法

给你n张纸片，正反面写有字母。问怎样排列这些纸片，能够排出来给定的句子。所有纸片都要用到。
用dfs可以，优化可以使用trie。求Trie的解法。

这不是标准二分图完美匹配吗？左边An节点代表目标字符串，右边Bn节点代表卡片，对于每个目标字符Ai，将其和出现该字符的每个卡片Bj连一条边，然后匈牙利算法。

构造一个图。左面一排结点是每张纸片，源点到每张纸片有权重为1的边。右面一排结点是每个字母，每张纸片有两个权重为1的边连接正反两个字母。字母如果在句子中出现，有一条权重为出现次数的边连到汇点。答案就求源点到汇点的最大流。

这道题DFS的问题是有正反面，而且要求全部用完，所以没办法做memo，会导致最后复杂度退化成Backtracking

用Trie的话我觉得应该是把所有卡片上的单词做成Trie，同时TrieNode不仅要有isWord，还需要标注isWord==True的时候卡片的index。
可能有多张卡片是同一个单词，所以实际上TrieNode上是一个card index set

然后需要逐词遍历那个句子。在第一个词的时候，根据结束的index set，你拿到的是一个可以作为序列开始的卡片的集合。接下来你把这个集合想象成到这个词为止，可能的一条“path”，后面的逐词遍历实际上就是根据path和trie去删除不可能的path，比如遍历到某一个词的时候其中一条path上已经拿不出对应的node了，那么就把它删掉。这样直到最后一个词就可以找到合法的path

如果卡片上的词最长为L，那么Trie的树高为L；一共有K张卡片，句子的词数为M，每个词的长度最大为N，上面那种方法的复杂度应该是：
K*L*M，和句子中的词长度无关，因为我们只在Trie上遍历

如果用DFS尝试所有的组合，那复杂度应该是K!，理论上大概率会比用Trie慢

zhmingrui 发表于 2021-6-2 22:42
构造一个图。左面一排结点是每张纸片，源点到每张纸片有权重为1的边。右面一排结点是 ...

无权二部图最大匹配可以reduce为最大流

用dfs，然后trie剪枝？boggle game那题的trie改造一下即可

呆鹅 发表于 2021-6-2 01:15
这不是标准二分图完美匹配吗？左边An节点代表目标字符串，右边Bn节点代表卡片，对于每个目标字符Ai，将其和 ...

为什么用hungarian algo? 这不是optimization 问题