📣 VIP通行证夏日特惠 限时立减$68
楼主: love1point
跳转到指定楼层
上一主题 下一主题
收起左侧

Longest words

🔗
 楼主| 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[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. };
复制代码



其他一样。不知觉得如何?
回复

使用道具 举报

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

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

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

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

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

评分

参与人数 1大米 +5 收起 理由
love1point + 5 欢迎和欢迎你的讨论哈

查看全部评分

回复

使用道具 举报

🔗
 楼主| 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, “好莱坞之王”。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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