求问这道算法题有什么好的解法吗？

给一个想要读的书单， 实现boolean match(String[] books)这个function，来判断输入的books是不是在想要读的书单里。 注意书单里出现的 * 属于wild card，在匹配时可以代表任何书。

举例： 如果想要读的书单是[["book1", "*", "book2"], ["book3", "book4", "*"]],
1. 输入如果是["book1", "book5", "book2"]，需要return true，因为书单里有["book1", "*", "book2"]和输入成功匹配。
2. 输入如果是["book3", "book5", "book4"]，需要return false，因为书单里没有匹配的元素。

请问这题除了brute force方法外有什么更高效的解法吗？

你这第二个不是也在书单里啊？ 第二个不是吗？

字典树 AC自动机感觉可以？

欧文市长 发表于 2022-6-13 17:13
你这第二个不是也在书单里啊？ 第二个不是吗？

顺序也必须一致的，第二个书单的第二个元素是book4, 但是第二个输入第二个元素是book5，所以没法匹配

shaosy 发表于 2022-6-13 17:31
字典树 AC自动机感觉可以？

我也觉得应该需要建树来优化这个function的时间复杂度，不过目前还没想好怎么处理wildcard... 感觉search的时候需要在树上递归？

AndromedaX 发表于 2022-06-13 02:52:07
我也觉得应该需要建树来优化这个function的时间复杂度，不过目前还没想好怎么处理wildcard... 感觉search的时候需要在树上递归？

wildcard就把所有子节点扔进匹配list就好了啊，走不下去的剪枝

用一个trie记录书单，然后每个qury 从trie root开始 去查每个输入，dfs找match 的名字 或者*？

如果想要读的书单是[["book1", "*", "book2"], ["book3", "book4", "*"]],
1. 输入如果是["book1", "book5", "book2"]，需要return true，因为书单里有["book1", "*", "book2"]和输入成功匹配。
2. 输入如果是["book3", "book5", "book4"]，需要return false，因为书单里没有匹配的元素。
请问这题除了brute force方法外有什么更高效的解法吗？

找个难道不是字符匹配的变种吗？

假定一共有26本书，分别是26个字符'a', 'b', 'c', 'd'..... 'z'

这个问题转化为
如果想要读的书单是[["a", "*", "b"], ["c", "d", "*"]],
1. 输入如果是["a", "e", "b"]，需要return true，因为书单里有["a", "*", "b"]和输入成功匹配。
2. 输入如果是["c", "e", "d"]，需要return false，因为书单里没有匹配的元素。

上面起始就是问 "a*b" 是不是匹配 “aeb"

比较好想的方法，建立单词->数字的hash，然后把数字当关键字建trie，碰见wildcard就所有分支全找一遍（本质上是dfs或者bfs）
优化1：对于每一层，记录所有书单中是否出现过这个单词。用处比较小，而且一旦任何一个书单在这个位置有wildcard就破了
优化2：正反向各建一个trie，双向找，碰头就算找到（类似双向bfs）
不过这两个优化效果都一般般吧