Longest words

glaciersilent 发表于 2015-6-9 09:39
maintain一个这样的hashmap感觉是overkill啊 只问了最长的词的list，map里存的短词的entry都是浪费内存啊。 ...

感谢你的分析哈，根据你的算法1的two pass，我实现了它且AC过了并且贴在下面，需要的同学请拿走哈

1. class Solution {
   
2.     /**
   
3.      * @param dictionary: an array of strings
   
4.      * @return: an arraylist of strings
   
5.      */
   
6.     ArrayList<String> longestWords(String[] dictionary) {
   
7.         // write your code here
   
8.         ArrayList<String> result = new ArrayList<String>();
   
9.         int max = 0;
   
10.         for(int i = 0; i < dictionary.length; i++)
    
11.         {
    
12.             max = Math.max(dictionary[i].length(), max);
    
13.         }
    
14.         
    
15.         for(String a : dictionary)
    
16.         {
    
17.             if(a.length() == max)
    
18.             {
    
19.                 result.add(a);
    
20.             }
    
21.         }
    
22.         return result;
    
23.     }
    
24. };
    

复制代码

如果这个题加一个follow up，变成：“找出所有具有某个特定前缀的单词中最长的那些”。例如:

字典为：{"prep", "prenup", "president", "precision", "previewer", "professional", "internationalization"}
待查找前缀为：“pre”
结果：{ "president", "precision", "previewer"}

楼主会怎么解？

stellari 发表于 2015-6-9 15:46
如果这个题加一个follow up，变成：“找出所有具有某个特定前缀的单词中最长的那些”。例如:

字典为：{ ...

我第一反应，加两个判断，在上面那个双重循环的方法。第一个判断单词长度至少大于等于3，嵌在第一个if里加上第二个判断，用 dictionary[i].substring(0,3).equals("pre"). 用hashmap的方法就是在循环里加这两个判断。

1. class Solution {
   
2.     /**
   
3.      * @param dictionary: an array of strings
   
4.      * @return: an arraylist of strings
   
5.      */
   
6.     ArrayList<String> longestWords(String[] dictionary) {
   
7.         // write your code here
   
8.         ArrayList<String> result = new ArrayList<String>();
   
9.         int max = 0;
   
10.         for(int i = 0; i < dictionary.length; i++)
    
11.         {  if(dictionary[i].length()>=3)
    
12.          {  
    
13.               if(dictionary[i].substring(0,3).equals("pre")){  max = Math.max(dictionary[i].length(), max);
    
14.          }
    
15.             
    
16.         }
    
17.         
    
18.         for(String a : dictionary)
    
19.         {
    
20.             if(a.length() == max)
    
21.             {
    
22.                 result.add(a);
    
23.             }
    
24.         }
    
25.         return result;
    
26.     }
    
27. };

复制代码

。


其他一样。不知觉得如何？

love1point 发表于 2015-6-9 16:20
我第一反应，加两个判断，在上面那个双重循环的方法。第一个判断单词长度至少大于等于3，嵌在第一个if里 ...

嗯，这想法可以。不过第二个循环中应该还需要再判断a的前缀是否为“pre”。 因为dictionary中可能存住着大量的长度等于max，但是前缀却不是"pre"的单词。

看楼主这么有激情咱再来个follow up？
--------------------------
假设：

词典非常非常大；
需要非常频繁地进行“特定前缀最长词”的查询；
查询返回的结果数通常远小于词典的长度。

在这种情况下，又该如何设计程序使之能够满足这种情况的需要？允许对词典进行预处理。

stellari 发表于 2015-6-9 16:55
嗯，这想法可以。不过第二个循环中应该还需要再判断a的前缀是否为“pre”。 因为dictionary中可能存住着 ...

对哈，我忘了也需要对第二个需要进行判断。多谢提醒

----------------------------------
你的follow up:

看到“非常频繁地...进行查询”这几个关键词，我想到用哈希的方法，因为哈希取数据是o(1)。那就先对字典进行HashMap???

--------------------------
P.S. 你是哪家的面试官    啊 or 不？

love1point 发表于 2015-6-9 17:04
对哈，我忘了也需要对第二个需要进行判断。多谢提醒

----------------------------------

在下同样是求职者。我只是觉得如果我是面试官的话，我多半会问出这样的问题。
---------------
对，“非常频繁地”通常的意思就是“要尽可能地快”。原来的方法每次查询都要整个扫一遍dictionary，每个词上面至少要花掉O(length(prefix))时间。而最后的结果只是词典的很小的一个子集。这样不太有效。

HashMap确实是一个可能的思路。总之，我们希望能有一个“特别设计”的HashMap，通过这个HashMap能快速找到满足任意前缀要求的单词。你会怎么做？如果只是把所有的单词本身放到HashMap中显然是不行的，因为那样我们没法查询前缀。

---------------

stellari 发表于 2015-6-9 17:59
在下同样是求职者。我只是觉得如果我是面试官的话，我多半会问出这样的问题。
---------------
对，“ ...

不太清楚了。

要是我用HashMap，我只会在循环里加判断然后在处理。我没想那么远哈

love1point 发表于 2015-6-9 18:16
不太清楚了。

要是我用HashMap，我只会在循环里加判断然后在处理。我没想那么远哈

如果考官明确提到了“查询前缀”这样的字样，那么你的思路可能需要往前缀树 (Trie)上去靠。这个题我觉得前缀树应该是最佳解法。在每个Trie节点上维护一个“从本节点开始的最长词的长度”MaxLen。

首先在Trie上找“pre”这个前缀。找到以后，看e对应的节点处的MaxLen是多少。如果是6，那么就知道最长单词长度肯定是6 +3 =9。我们可以从e这个节点开始做DFS或BFS。如果某一层的MaxLen不符合预期，那么这一层及其以下的节点就都不用看了。该方法找一个长为L的词只需要O(L)的时间。总复杂度是O(len(result) * len(longest word))。这个时间大大短于原来的O(len(dict) * length(prefix))

你也可以用一个HashMap来模拟前缀树。HashMap大概会长这个样子：
{"p": {"pr", "pi", "pl"},
"pr": {"pre", "pro", "pra"},
"pl": {"pla", "plu", "ple"},
...
"pre": {"pres", "prec", "prev", "prep", "pren"}
"pres": {"presi"}
"presi": {"presid"}
...
}
但是，这样会非常非常耗费内存。不推荐这种做法。

stellari 发表于 2015-6-9 19:15
如果考官明确提到了“查询前缀”这样的字样，那么你的思路可能需要往前缀树 (Trie)上去靠。这个题我觉得 ...

恩。多谢详细分析。我只听过trie,但从来没用过哈。

你头像是哪个演员啊？

love1point 发表于 2015-6-9 19:25
恩。多谢详细分析。我只听过trie,但从来没用过哈。

你头像是哪个演员啊？

Leetcode和Lintcode上都有Trie相关的题。你不妨去看看。Trie是非常有用的数据结构。

Clark Gable， “好莱坞之王”。