pinterest 电面跪经

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

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

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

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

feifeiguoguo 发表于 2017-10-31 01:14
这个只要字典里有world就会输出world了。输出的是字典里长度最长的单词。不知道是不是建好之后需要DFS， ...

哦哦哦，我考虑的太简单了，上来我觉得应该按照一个规则进行排序才对

perry1990 发表于 2017-10-31 01:14
这个是这道题基本功能的实现。
我比较好奇的是，这道题怎么保证 'w', 'wo', 出现在world之前呢。按道理 ...

嗯嗯，是的，考虑太简单了，如果这样的话加上一个排序应该可以控制w wo wor的先后顺序

perry1990 发表于 2017-10-31 01:14
这个是这道题基本功能的实现。
我比较好奇的是，这道题怎么保证 'w', 'wo', 出现在world之前呢。按道理 ...

如果存在w wo wor world这种情况的话，代码就得更多了

1. public class BuildDict {
   
2. 
   
3.     public static TrieNode root;
   
4. 
   
5.     public static void main(String[]args){
   
6.         String[] dict = {"world", "wo", "wt", "wor", "w", "worl", "wto"};
   
7.         System.out.println(maxWord(dict));
   
8.     }
   
9. 
   
10. 
    
11.     public static String maxWord(String[] dict){
    
12.         if(dict == null || dict.length == 0) return "";
    
13.         Map<String, Integer> map = new HashMap<>();
    
14.         Queue<String> queue = new LinkedList<>();
    
15.         for(String word : dict){
    
16.             if(word.length() == 1) {
    
17.                 queue.add(word);
    
18.             }
    
19.             map.put(word, 0);
    
20.         }
    
21.         String res = "";
    
22.         while(!queue.isEmpty()){
    
23.             int size = queue.size();
    
24.             for(int i = 0; i < size; i++){
    
25.                 String word = queue.poll();
    
26.                 for(char c = 'a'; c <= 'z'; c++){
    
27.                     String tmpWord = word + c;
    
28.                     if(map.containsKey(tmpWord)){
    
29.                         queue.add(tmpWord);
    
30.                         res = tmpWord;
    
31.                     }
    
32.                 }
    
33.             }
    
34.         }
    
35.         return res;
    
36.     }
    
37. }

复制代码

重新写了一版，感觉不用trie也好，用bfs，从1个字符的word开始，有点点像word ladder，楼主提到如果有多个同样长度的话，返回随便一个就好的话，不断更新的话，最后queue空的时候，最后更新的值就是最大长度的word了。还请各位大神指教

feifeiguoguo 发表于 2017-10-31 01:14
这个只要字典里有world就会输出world了。输出的是字典里长度最长的单词。不知道是不是建好之后需要DFS， ...

我就是这么做的，建立一个trie，然后dfs

这题就是 LC原题：

https://leetcode.com/problems/longest-word-in-dictionary/description/

补充内容 (2017-11-15 15:51):
好吧，严格地说，很有可能楼主面试是在leetcode加了这题之前。所以Pinterests的面试题确实有点小难。。

LeeYYY 发表于 2017-11-15 15:37
这题就是 LC原题：

https://leetcode.com/problems/longest-word-in-dictionary/description/

感觉就是从我这个帖子过去的。。。

sunyanzi 发表于 2017-11-17 06:26
感觉就是从我这个帖子过去的。。。

神了！楼主威武啊