在一次面试中,我被要求设计一种数据结构,它可以容纳数百万个模式,并能快速搜索以找到最长匹配的模式。
例如,模式可能是以下这样的:
1- 8876 8893 87 | true
2- 8876 889 | false
3- 8876 8 | false
4- 887 | true
输入是一个至少有2位数、最多有18位数的数字,我们需要从数据结构中找到最长匹配模式,并提取末尾的布尔值。
例如,
8876 8893 9943 53
将匹配1
,并返回true
。 8876 8397 5430 74
将匹配3
,并返回false
。我的答案是使用一棵树,在每个级别上有一个
key value
对的列表。 键是数字,值为null或布尔值,具体取决于它是否是模式的结尾。像这样:# matching 8875
# start the search by first digit
[..., (7, null), (8, null), (9, null)]
^
[..., (7, null), (8, null), (9, null)]
^
[..., (7, true), (8, null), ...]
# at the last step because we don't have a pattern
# to match the digit 5, we return the `true` from (7, true)
挑战在于,这些模式非常多。有数百万种。这有好处吗?如果没有,您有什么建议。