Snapchat 电面.10分钟以前

glad2mu 发表于 2016-12-14 02:58
是不是用trie 来存储词典然后用dfs 搜索这个trie. 碰到isend to true 加到结果里 然后继续向下找。 用hashs ...

"isend to true" 是什么意思

freemail165 发表于 2016-12-15 15:31
"isend to true" 是什么意思

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

幻灭天神 发表于 2016-12-18 07:12
用Trie+DFS写的

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

敢问楼主这样为什么会挂，如果能在面试短时间里把这个写出来而且跑通，真的非常厉害了....

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

贴个代码。

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. 
   
8.         List<String> result = new ArrayList<>();
   
9.         for (String s : dict) {
   
10.             Map<Character, Integer> map = new HashMap<>();
    
11.             boolean found = true;
    
12.             for (int i = 0; i < s.length(); ++i) {
    
13.                 char c = s.charAt(i);
    
14.                 map.put(c, map.getOrDefault(c, 0) + 1);
    
15.                 if (map.get(c) > table[c]) {
    
16.                     found = false;
    
17.                     break;
    
18.                 }
    
19.             }
    
20.             if (found) result.add(s);
    
21.         }
    
22. 
    
23.         return result;
    
24.     }
    
25. 
    
26.     public static void main(String[] args) {
    
27.         char[] array = {'A', 'B', 'C', 'A'};
    
28.         List<String> dict = Arrays.asList("AA", "BB", "A", "BA");
    
29.         WordSearch wordSearch = new WordSearch();
    
30.         List<String> result = wordSearch.findWord(array, dict);
    
31.         for (String s : result) {
    
32.             System.out.println(s);
    
33.         }
    
34.     }
    
35. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies