uber 店面

楼上是正解，我也也觉得是考查revert index

借楼问一下，我面过一道差不多的题目，只是返回不是true/false而是string里包含所有character的最短substring长度。当时用two pointer做的，请问这样做是对的吗

我觉得可以借用group of anagram 的思想，对dictionary预处理。同样anagram的words 放到一个list里，然后anagram作为key. 用array of chars构造一个key，如果能找到，那返回的就是最短的word list.

wwendywang 发表于 2017-6-20 06:32
我觉得可以借用group of anagram 的思想，对dictionary预处理。同样anagram的words 放到一个list里，然后an ...

首先是anagram的重复率应该不算高
其次，你按anagram排了以后，并没有形成特别有效的索引啊

比如给的['k', 'z']
你要怎么找到所有对应的anagram呢？
貌似还是要O(n)的复杂度吧

对dictionary 预处理肯定是要O(n)的时间复杂度。 anagram 的索引可以用prime 做，或者直接做成 string。譬如['k', 'z'] 可以是 31*103, 也可以是KZ.
如果你要找 ['z', 'k'], O(1) 就可以 找到。

我们先不讨论质数溢出的问题   

你能讲解下O(1)的步骤吗？
我理解你的方法是用anagram的积挨个儿去除31×103

wwendywang 发表于 2017-6-20 13:37
对dictionary 预处理肯定是要O(n)的时间复杂度。 anagram 的索引可以用 prime 做，或者直接做成 string。譬 ...

我们先不讨论质数溢出的问题   

你能讲解下O(1)的步骤吗？
我理解你的方法是用anagram的积挨个儿去除31×103

['z', 'k']是103*31, 等于31*103. 在预处理好的字典map里可以直接找到. 如果假设array是排好序的，只有 ['k', 'z'] 这一种情况，那build一个string - KZ, 也可以直接在预处理好的字典map里找到。如果KZ没有， 那就加一个a, 看看akz 是不是在map里，然后加一个b, 看看bkz在不在，依此类推，可以找到最短的string. 这样的情况，就不是O(1)了。

revert index 好像比较对，这个和word and document 应该是一样的