谷歌面经题 wild card match

Job Hunting Interview
,
1

别的地方看来的面经题。用trie怎么存wildcard?

给你一堆filter， 把满足filter 条件的单词选择出来。 比如 filter 是 ［he*o, a*p］ 那么 ‘hello’ 和 ‘heo’ 满足第一个filter。 就是‘＊’ 可以match 任何数量的字母， 0 到multiple。 如果input是 ‘banana’就一个filter 都不符合。 要求实现两个函数。
1.要把所有的filter 存起来 （这个应该是第一个函数）。
2.input 一个单词，判断对于所有的filter， 是否filter 成功， 比如这里 hello 就是true，banana就是false.
楼主选择了了把所有filter 存在了set里，然后做for loop，filter 一旦成功了就返回true. 写完了后小哥问能提高复杂度么？ 我一时没想出来，小哥也不给hint， 我就说也可以dp 做， （我用的dfs） 但时间复杂度一样。 小哥不说话，我就开始写dp的推导公式，然后小哥终于发话了，说dp 也不会加快，你想想还能怎么存 filters, 然后我说可以存成trie。 小哥点点头。 然后大致讲了讲如果用trie 的话怎么写， 这一问没有写code。

2

这题出现频率挺高的，你确定正确思路是用 Trie 吗？

3

狗家还有这么一道题

  1. Some IDEs let you type a non-contiguous substring of the file name in order to search and open a file. Write a method that takes a pattern and a filename and returns whether or not the pattern is a non-contiguous substring of the filename. For instance, pattern “Mav” is a non-contiguous substring of “MyJavaClass.java”. “MM” is not.

  2. Usually the IDE will let you type and when you pause, it will display the current list of matches. Pretend you’re working on a team for this feature. Someone else is in charge of UI and collecting the current pattern whenever the user pauses. Write a utility that will take the pattern and return a list of the current matches. For example, if the user input is: Mava 1st call: “Ma” 2nd call: “Mav” 3rd call: “Mava”

其实就是 subsequence 的题型。这里的 * 其实就是隐含的。

4

看一下 leetcode 792 是否有帮助

  1. Number of Matching Subsequences

Given string S and a dictionary of words words , find the number of words[i] that is a subsequence of S .

Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".
5

您这么一说确实感觉就是792变种

6

但不一样的地方是subsequence ‘abc’ 用wildcard表示相当于’a*b*c’, 没有办法表示例如’ab*c’形式的pattern.
792把subsequeces按首字母放bucket的解法好像就行不通了

7

首先我个人觉得 Trie 不适合做这个， Trie 对 * 的操作没有优势

8

这里可以这样试试

比如 word 是 Hello， wildcard 是 ["He*o", "*ll*"]

对应产生的Map<String, Integer> 是 <“He” -> 0, “ll” -> 1>, 0 是"He*o"的index，1是"*ll*"的index
Match 某个 key 的时候需要全部走完，也就是说 “He” match好了Map就是
<“o” -> 0, “ll” -> 1>

9

说的不对，这里的Map是 <Character, List<Pair<String, Integer>>>
key是* split后的substring的首字母，value 是个Pair

["He*o", "*ll*"]

对应的是

<H -> [{He, 0}], l -> [{ll, 1}]>

另外Pair 可能不够，用Tuple，还需要存 substring match后的对应的word 的 begin index

进一步优化，可以记录所有的wild card 的substring match后的下一个begin index的最小值

11

另一点和subsequence不一样的地方，wildcard matching可能对ending letters有要求，比如a*ab，就必须以ab结尾。而subsequence对结尾没有要求，所以可以greedy去match。

另外LC 上wildcard matching复杂度是O(len(pattern) * len(input_string))，而subsequence可以做到linear。感觉subsequence套路应该解不了wildcard matching吧？

12

这里只要记下相应的index，检查一下就可以了。等于在subsequence的基础上增强一下

13

这里的 Map 我再进一步解释一下
key 是 Character, value 的 class 如下

    class Bucket {
        List<Integer> indexes; // index in original wildcard array
        String s; // substring split by *
        List<Integer> begIndex; // begin index of word for corresponding wild card
    }
14

你解这题可能用的是DP，但其实不用。
可以先处理一下pattern，比如 "*ab*c**d*" => [ab, c, d]

这里对于首或尾不是 * 的情况要处理一下：如果首或尾不是 * ，需要严格直接首或尾 match
比如 "c*ab*c**d*c" => [ab, c, d]， word是ccabbcccdc, 首和尾的c必须跟word的首和尾对应，
所以word就变成了 cabbcccd
pattern处理完就一定两边都是 *
本身 * 就是最麻烦的地方

15

Trie 的话可能可以参考 745. Prefix and Suffix Search

Given many words , words[i] has weight i .

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix) . It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1

这题我在Trie专题讲过

可以参考文档

image

image

16

这题前面说了两种思路，虽然相关，但是都没有针对该题的特殊性

image

这题关键在于，是先把filter处理，而第2步仅仅传进来一个word，只要有一个 filter 不符合那就返回 false。
这里我们看下第1步，比如 He* 和 Hel* 相当于 一个 Hel*，He*没有意义。也就是我们其实可以把所有的wildcard 合并成一个。

17

这里是不是我理解错了，这里所有的filter 其实是OR的操作，并不是 AND 吧。也就是说只要有一个filter返回true，第2步返回true :sweat_smile:

是不是可以把上述两种思路结合起来
先用 745. Prefix and Suffix Search ，这样filter剩下的就是两边都是*的了。
比如 "c*ab*c**d*c" => "*ab*c**d*" => [ab, c, d]，这里首和尾的 c 就已经放到Trie里去里。Trie最终下来的node 指向这个[ab, c, d]对应的map

18

好吧，这题我觉得正解就是 745. Prefix and Suffix Search 因为这样处理后，prefix和suffix相同的filter还能有多少呢？一般也就一个吧。经过prefix和suffix处理，剩下的即使暴力破解也无妨，因为一般也就剩下一个filter了。而且思路上是符合面试官要求的Trie。