Longest words

有人说下面这道google曾经考过，谁有比较好的解法不？

题目链接：http://www.lintcode.com/en/problem/longest-words/

补充：其实这题最关键的地方就是如何记入下最长单词的长度，避免出现遗漏相同长度的单词。昨晚问了大家这道题，好几个同学都给了我非常快且好的算法，再次感谢一亩三分地这个平台，能让我们的疑问得到解答。所以，只要我们互相提供信息，我们都能得到我们需要的。赞扬这种不仅从地里获得东西，还给予的网友！

[b]Easy

Longest Words[/b]

40%Accepted

Given a dictionary, find all of the longest words in the dictionary.

Have you met this question in a real interview?

Yes

Example

Given

{  "dog",  "google",  "facebook",  "internationalization",  "blabla"}

the longest words are(is) ["internationalization"].

Given

{  "like",  "love",  "hate",  "yes"}

the longest words are ["like", "love", "hate"].

class Solution {

    /**

     * @param dictionary: an array of strings

     * @return: an arraylist of strings

     */

    ArrayList<String> longestWords(String[] dictionary) {

        // write your code here

    }

};

maintain一个这样的hashmap感觉是overkill啊 只问了最长的词的list，map里存的短词的entry都是浪费内存啊。太fancy的解法我想不出来，我感觉两次扫描，第一次扫描得出最长词的长度，第二次扫描添加最长词，这样不消耗额外内存。要非得一遍扫，可以ArrayList保存当前最长词序列 一旦发现更长的词就clear 然后添加更长词。

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. };

复制代码

。


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

献上我AC过的代码。

感觉google真的很爱考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.         HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
   
10.         
    
11.         int max = 0;
    
12.         for(int i = 0; i < dictionary.length; i++)
    
13.         {
    
14.             if(map.containsKey(dictionary[i].length()))
    
15.             {
    
16.                 map.get(dictionary[i].length()).add(dictionary[i]);   
    
17.             }
    
18.             else
    
19.             {
    
20.                 ArrayList<String> arr = new ArrayList<String>();
    
21.                 arr.add(dictionary[i]);
    
22.                 map.put(dictionary[i].length(), arr);
    
23.             }
    
24.             max = Math.max(dictionary[i].length(), max);
    
25.         }
    
26.         return map.get(max);
    
27.     }
    
28. };
    

复制代码

遍历一遍，用一个map存下来，key是单词的长度，value是vector<string>

1. class Solution
   
2. {
   
3. public:
   
4.     vector<string> longestWords(vector<string>& dict)
   
5.     {
   
6.         map<size_t,vector<string> > m;
   
7.         size_t maxLength = 0;
   
8.         for(auto it = dict.begin(); it != dict.end(); ++it)
   
9.         {
   
10.             maxLength = std::max(it->length(), maxLength);
    
11.             m[it->length()].push_back(*it);
    
12.         }
    
13. 
    
14.         return m[maxLength];
    
15.     }
    
16. };
    

复制代码

cloudending 发表于 2015-6-8 21:51
遍历一遍，用一个map存下来，key是单词的长度，value是vector

你能把算法思想写一下不？谢谢。C++我不怎么熟。你用java也行。

这题如果有长度一样的单词这种情况我好像卡住了

cloudending 发表于 2015-6-8 21:51
遍历一遍，用一个map存下来，key是单词的长度，value是vector

我的解法还是只能输出一个，无法输出相同长度的单词。
比如 map 后（3，“abc”）, (3, "def")
还是只能输出一个

[i][i]

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.         HashMap<Integer, String> map = new HashMap<Integer, String>();
   
9.         ArrayList<String> result = new ArrayList<String>();
   
10.         
    
11.         int max = 0;
    
12.         
    
13.         for(int i = 0; i < dictionary.length; i++)
    
14.         {
    
15.             max= Math.max(dictionary.length(), max);
    
16.             map.put(dictionary.length(), dictionary);
    
17.         }
    
18.         
    
19.         for(Integer a : map.keySet())
    
20.         {
    
21.             if(a == max)
    
22.             {
    
23.                 result.add(map.get(a));
    
24.             }
    
25.         }
    
26.         return result;
    
27.     }
    
28. };

复制代码

[/i][/i]

love1point 发表于 2015-6-8 22:49
我的解法还是只能输出一个，无法输出相同长度的单词。
比如 map 后（3，“abc”）, (3, "def")
还是只 ...

你需要维护一个
HashMap<Integer, ArrayList<String>>
来建立
“单词长度->所有符合该长度的单词的列表”
这样的映射。

比如词典中是{"a", "ad","to", "red","but", "car"};
那么你建立的Map就是
{{1: {"a"}}, {2: {"ad", "to"}}, {3: {"red", "but", "car}}}.

有了这样的一个Map你就可以直接从中取得结果了。

stellari 发表于 2015-6-9 00:21
你需要维护一个
HashMap
来建立

非常感谢。

经过你的点播，V 变成 ArrayList<String> 很好的解决了我的问题，再也不会漏了长度一样的字符串。

love1point 发表于 2015-6-8 22:13
你能把算法思想写一下不？谢谢。C++我不怎么熟。你用java也行。

这题如果有长度一样的单词这种情况我 ...

嗯，楼上的一样，这里的vector是vector<string>，就相当于java的ArrayList<String>

cloudending 发表于 2015-6-9 09:10
嗯，楼上的一样，这里的vector是vector，就相当于java的ArrayList

好的，非常感谢