📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: 弱视个体
跳转到指定楼层
上一主题 下一主题
收起左侧

Snapchat 电面.10分钟以前

🔗
freemail165 2016-12-15 15:31:43 | 只看该作者
全局:
glad2mu 发表于 2016-12-14 02:58
是不是用trie 来存储词典然后用dfs 搜索这个trie. 碰到isend to true 加到结果里 然后继续向下找。 用hashs ...

"isend to true" 是什么意思
回复

使用道具 举报

🔗
glad2mu 2016-12-16 02:08:42 | 只看该作者
全局:
freemail165 发表于 2016-12-15 15:31
"isend to true" 是什么意思

isend就是trie node里面用来标记是不是单词结尾的flag.   我原来的意思就是在trie里搜索 发现一个单词后继续向下搜索
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
zhhan1990 2016-12-20 16:11:09 | 只看该作者
全局:

你这样子实现trie非常浪费空间,可以考虑每个node的子节点数组用hashmap来存,当然如果在alphabet小的情况下,两者空间利率用差不多。
回复

使用道具 举报

🔗
3d596d24 2016-12-20 20:45:17 | 只看该作者
全局:
敢问楼主这样为什么会挂,如果能在面试短时间里把这个写出来而且跑通,真的非常厉害了....
回复

使用道具 举报

🔗
shoppinglee 2016-12-21 14:56:12 | 只看该作者
全局:
 这个题目我觉得把array里的char用HashMap计数。然后对于字典里的每个单词,用LinkedHashMap统计下出现字母的count,然后iterate一下key, value,只要所有出现字母的count都比原来array生成的那个hashMap里面的计数小,就满足条件了啊。。。我感觉完全不需要用Trie这种很麻烦的数据结构。。。
回复

使用道具 举报

🔗
shoppinglee 2016-12-21 15:23:48 | 只看该作者
全局:
贴个代码。

  1. public class WordSearch {
  2.     public List<String> findWord(char[] array, List<String> dict) {
  3.         int[] table = new int[256];
  4.         for (char c : array) {
  5.             table[c]++;
  6.         }

  7.         List<String> result = new ArrayList<>();
  8.         for (String s : dict) {
  9.             Map<Character, Integer> map = new HashMap<>();
  10.             boolean found = true;
  11.             for (int i = 0; i < s.length(); ++i) {
  12.                 char c = s.charAt(i);
  13.                 map.put(c, map.getOrDefault(c, 0) + 1);
  14.                 if (map.get(c) > table[c]) {
  15.                     found = false;
  16.                     break;
  17.                 }
  18.             }
  19.             if (found) result.add(s);
  20.         }

  21.         return result;
  22.     }

  23.     public static void main(String[] args) {
  24.         char[] array = {'A', 'B', 'C', 'A'};
  25.         List<String> dict = Arrays.asList("AA", "BB", "A", "BA");
  26.         WordSearch wordSearch = new WordSearch();
  27.         List<String> result = wordSearch.findWord(array, dict);
  28.         for (String s : result) {
  29.             System.out.println(s);
  30.         }
  31.     }
  32. }
复制代码
回复

使用道具 举报

🔗
jyty 2016-12-29 05:03:34 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

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

本版积分规则

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