一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2253|回复: 23
收起左侧

[算法题] Longest words

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-8 21:27:06 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 love1point 于 2015-6-9 09:56 编辑

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

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

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

Easy
Longest Words


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






glaciersilent 发表于 2015-6-9 09:39:23 | 显示全部楼层
maintain一个这样的hashmap感觉是overkill啊 只问了最长的词的list,map里存的短词的entry都是浪费内存啊。太fancy的解法我想不出来,我感觉两次扫描,第一次扫描得出最长词的长度,第二次扫描添加最长词,这样不消耗额外内存。要非得一遍扫,可以ArrayList保存当前最长词序列 一旦发现更长的词就clear 然后添加更长词。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

cloudending 发表于 2015-6-8 21:51:15 | 显示全部楼层
遍历一遍,用一个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.         return m[maxLength];
  14.     }
  15. };
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-8 22:13:11 | 显示全部楼层
cloudending 发表于 2015-6-8 21:51
遍历一遍,用一个map存下来,key是单词的长度,value是vector

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

这题如果有长度一样的单词这种情况我好像卡住了
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-8 22:49:26 | 显示全部楼层
本帖最后由 love1point 于 2015-6-8 22:50 编辑
cloudending 发表于 2015-6-8 21:51
遍历一遍,用一个map存下来,key是单词的长度,value是vector

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

  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. };
复制代码
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-9 00:21:13 | 显示全部楼层
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你就可以直接从中取得结果了。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-9 01:53:28 | 显示全部楼层
stellari 发表于 2015-6-9 00:21
你需要维护一个
HashMap
来建立

非常感谢。

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

使用道具 举报

 楼主| love1point 发表于 2015-6-9 01:55:03 | 显示全部楼层
献上我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. };
复制代码
回复 支持 反对

使用道具 举报

cloudending 发表于 2015-6-9 09:10:08 | 显示全部楼层
love1point 发表于 2015-6-8 22:13
你能把算法思想写一下不?谢谢。C++我不怎么熟。你用java也行。

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

嗯,楼上的一样,这里的vector是vector<string>,就相当于java的ArrayList<String>
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-9 09:11:30 | 显示全部楼层
cloudending 发表于 2015-6-9 09:10
嗯,楼上的一样,这里的vector是vector,就相当于java的ArrayList

好的,非常感谢
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-9 09:49:43 | 显示全部楼层
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. };
复制代码
回复 支持 反对

使用道具 举报

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

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

楼主会怎么解?


回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-9 16:20:19 | 显示全部楼层
stellari 发表于 2015-6-9 15:46
如果这个题加一个follow up,变成:“找出所有具有某个特定前缀的单词中最长的那些”。例如:

字典为:{ ...

我第一反应,加两个判断,在上面那个双重循环的方法。第一个判断单词长度至少大于等于3,嵌在第一个if里加上第二个判断,用 dictionary.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. };
复制代码



其他一样。不知觉得如何?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-9 16:55:05 | 显示全部楼层
love1point 发表于 2015-6-9 16:20
我第一反应,加两个判断,在上面那个双重循环的方法。第一个判断单词长度至少大于等于3,嵌在第一个if里 ...

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

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

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

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-9 17:04:37 | 显示全部楼层
stellari 发表于 2015-6-9 16:55
嗯,这想法可以。不过第二个循环中应该还需要再判断a的前缀是否为“pre”。 因为dictionary中可能存住着 ...

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

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

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

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


回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-9 17:59:46 | 显示全部楼层
love1point 发表于 2015-6-9 17:04
对哈,我忘了也需要对第二个需要进行判断。多谢提醒

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

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

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

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


回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-9 18:16:53 | 显示全部楼层
stellari 发表于 2015-6-9 17:59
在下同样是求职者。我只是觉得如果我是面试官的话,我多半会问出这样的问题。
---------------
对,“ ...

不太清楚了。

要是我用HashMap,我只会在循环里加判断然后在处理。我没想那么远哈
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-9 19:15:31 | 显示全部楼层
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"}
...
}
但是,这样会非常非常耗费内存。不推荐这种做法。
回复 支持 反对

使用道具 举报

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

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

你头像是哪个演员啊?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-9 21:56:13 | 显示全部楼层
本帖最后由 stellari 于 2015-6-9 22:12 编辑
love1point 发表于 2015-6-9 19:25
恩。多谢详细分析。我只听过trie,但从来没用过哈。

你头像是哪个演员啊?


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

Clark Gable, “好莱坞之王”。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 17:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表