G家实习电面挂经

jacky841102 发表于 2016-11-29 17:27
用了trie合并字典中的prefix
预处理S，把a~z在S中的index按照先后次序存进charList中
idxs表示目前各个ch ...

之前在另一个帖子里也看到这道题了，那个帖子里的google interviewer说是用trie做。好强，做这么用心的测试。google不要你要谁！

blactangeri 发表于 2016-11-30 11:40
你好 如果是求longest substring应该怎么做

这个问题很有意思：就是问字典中最长的单词长度，使得它是给定的string s的substring (instead of subsequence)。这样我想应该用BFS在字典Trie中做level order traversal，同时更新Trie node所代表的char在s中的index：从Trie root开始，定义index set={-1, 0,...,Ls-2} (Ls=s.length())，对于每个index, 在Trie的下一层看s[index+1]所代表的char在不在Trie中：root->next[s[index+1]-'a']==NULL?若在Trie中就可以加入下一层继续搜索。注意到在Trie同一层的nodes所对应的index set是disjoint，所以时间复杂度实际为O(Ls*min(Ls, Ld)) ，其中Ld=longest word length in dict (i.e., max depth of Trie).
(后来我想到原来的subsequence问题也许也应该用BFS比DFS更清楚一些)

1. int longestSubstr(string& s, const vector<string>& dict) {
   
2.   int ls = s.length(), maxlen = 0, count = -1;  Node* node = NULL;
   
3.   vector<int> indices; for (int i = 0; i < ls; ++i) indices.push_back(i - 1);
   
4.   unordered_map<Node*, vector<int>> idx = { { createTrie(dict, ls), indices } }, next_idx;
   
5.   while (!idx.empty()) { // Trie BFS level order traversal to update maxlen
   
6.     count++;
   
7.     for (auto& p : idx) // O(ls) for double loop since index sets are disjoint
   
8.       for (int i : p.second)
   
9.         if (i + 1 < ls && (node = p.first->next[s[i + 1] - 'a']))
   
10.         { next_idx[node].push_back(i + 1); if (node->isWord) maxlen = max(maxlen, count); }
    
11.     idx.clear(); swap(idx, next_idx);
    
12.   }
    
13.   return maxlen;
    
14. }

复制代码

jacky841102 发表于 2016-11-29 17:27
用了trie合并字典中的prefix
预处理S，把a~z在S中的index按照先后次序存进charList中
idxs表示目前各个ch ...

感谢测试！我在想Trie和brute force比较确实和具体的例子有关（字典单词prefix相似度，单词数量,etc），而且Trie的方法有很多overhead cost，所以若只对一个string s来说，建立Trie未必划算。
我在想这类问题是现实背景应该是什么？一般来说字典单词数量巨大，而且随时间变化频率很低，但对给定的string s很有可能要多次调用不同的s。可能要对实际情况的设定Trie的优势才能体现出来吧。

提供一个思路。用字典建trie，然后从string 的第一位开始，当找到匹配的children 以后 把该node push到vector里面，然后每次都需要 从root点查看一下。当到下一位的时候 轮询vector里面所有node 以及根结点，如果能够找到匹配的，node = node->children, 同时记录长度。这样 扫完string一遍以后就找到最长的了。当然这么做的问题是worse case是 O(n * m)  n 为string长度，m 为字典中单词个数。