Uber一面感觉要跪

刚刚结束的电面，感觉有点崩的。breakingbad，好像之前面经出现很多次，但是没有详细的介绍，把题想简单了。。

具体介绍一下这个题， input是String[] arr

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

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

这样。

开始太紧张了做了一会才开始急急忙忙的写Trie。

uber是不是一定要跑过才可以啊。。。好想哭。。。

1. public String format(String name, String[] array){
   
2.                 if(array.length == 0 || name == null || name.length() == 0){
   
3.                         return name;
   
4.                 }
   
5.                 Map<Character, Set<String>> dict = getDict(array);
   
6.                 StringBuilder sb = new StringBuilder();
   
7.                 for(int i=0; i<name.length(); ){
   
8.                         Character c = new Character(name.charAt(i));
   
9.                         String str = match(c, i, name, dict);
   
10.                         if(str.length()==0){
    
11.                                 sb.append(c);
    
12.                                 i++ ;
    
13.                         }else{
    
14.                                 sb.append("[").append(str).append("]");
    
15.                                 i+=str.length();
    
16.                         }
    
17.                 }
    
18.                 return sb.toString();
    
19.         }
    
20.        
    
21.         private String match(Character c, int index, String name, Map<Character, Set<String>> dict){
    
22.                 String maxMatch = "";
    
23.                 if(!dict.containsKey(c)){
    
24.                         return maxMatch;
    
25.                 }
    
26.                 Set<String> set = dict.get(c);
    
27.                
    
28.                 for(String s: set){
    
29.                         if(s.length() <= (name.length() - index)
    
30.                                         && name.indexOf(s) == index && s.length()>maxMatch.length()){                       
    
31.                                         maxMatch = s;
    
32.                         }
    
33.                 }
    
34.                
    
35.                 if(maxMatch.length()!=0){
    
36.                         maxMatch = maxMatch.replaceFirst(c.toString(), c.toString().toUpperCase());                       
    
37.                 }
    
38.                
    
39.                 return maxMatch;
    
40.         }
    
41.        
    
42.         private Map<Character, Set<String>> getDict(String[] array){
    
43.                 Map<Character, Set<String>> dict =  new HashMap<>();
    
44.                 for(String str:array){
    
45.                         str = str.toLowerCase();
    
46.                         Character c = new Character(str.charAt(0));
    
47.                         Set<String> set=dict.get(c);
    
48.                         if(set == null){
    
49.                                 set = new HashSet<String>();
    
50.                                 dict.put(c, set);
    
51.                         }
    
52.                         set.add(str.toLowerCase());
    
53.                 }
    
54.                 return dict;
    
55.         }

复制代码

1. class Main {
   
2.   static class TrieNode {
   
3.       char key;
   
4.       TrieNode[] children;
   
5.       boolean hasword;
   
6.       TrieNode(Character key) {
   
7.          
   
8.           children = new TrieNode[26];
   
9.           this.key = key;
   
10.           hasword = false;
    
11.       }
    
12.       TrieNode() {
    
13.           this.key = ' ';
    
14.           children = new TrieNode[26];
    
15.           hasword = false;
    
16.       }
    
17.   }
    
18.   
    
19.   static class TrieTree {
    
20.       TrieNode root;
    
21.       TrieTree() {
    
22.           root = new TrieNode();
    
23.       }
    
24.       public void insert(String word) {
    
25.           TrieNode cur = root;
    
26.           for (int i = 0; i < word.length(); i++) {
    
27.               if (cur.children[word.charAt(i) - 'a'] == null)
    
28.                   cur.children[word.charAt(i) - 'a'] = new TrieNode(word.charAt(i));
    
29.               cur = cur.children[word.charAt(i) - 'a'];
    
30.           }
    
31.           cur.hasword = true;
    
32.       }
    
33.   }
    
34.   private static String searchWords(String[] dict, String str) {
    
35.       TrieTree trietree = new TrieTree();
    
36.       for (int i = 0; i < dict.length; i++) {
    
37.           trietree.insert(dict[i]);
    
38.       }
    
39.       StringBuilder sb = new StringBuilder();
    
40.       int slow = 0, fast = 0;
    
41.       while (fast < str.length()) {
    
42.           TrieNode cur = trietree.root;
    
43.           int counter = 0;
    
44.           while (fast < str.length() && cur.children[str.charAt(fast) - 'a'] != null) {
    
45.               cur = cur.children[str.charAt(fast) - 'a'];
    
46.               counter++;
    
47.               fast++;
    
48.           }
    
49.           if (counter > 0) {//wrong: 忘记回退了.
    
50.               fast--;
    
51.               counter = 0;
    
52.           }
    
53.           if (cur.hasword) {//hasword 用于区分ddt是个词,但是不是个完整的词这个情况
    
54.               int i = slow;
    
55.               sb.append("[").append(Character.toUpperCase(str.charAt(i++)));
    
56.               while (i < fast) {
    
57.                   sb.append(str.charAt(i++));
    
58.               }
    
59.               sb.append("]");
    
60.           } else {
    
61.               sb.append(str.substring(slow, fast + 1));
    
62.           }
    
63.           fast++;
    
64.           slow = fast;
    
65.          
    
66.       }
    
67.       return sb.toString();
    
68.   }
    
69.   
    
70.   public static void main(String[] args) {
    
71.     String[] dict = {"b", "bc","cde", "e","tt","ertt","ddr"};
    
72.     String str = "abcdeddertte";
    
73.     System.out.println(searchWords(dict, str));
    
74.   }
    
75. }

复制代码

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

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

你写完Trie了应该没问题了吧？主程序应该就是一个loop了。

adrianliu729 发表于 2017-2-28 04:46
你写完Trie了应该没问题了吧？主程序应该就是一个loop了。

不知道bugfree重不重要。。哎

请问下楼主，这题就叫breakingbad吗？

请问怎么匹配bc呢。。。。字典里面不是只有Bc么

sherlockzzq 发表于 2017-11-14 11:40
请问怎么匹配bc呢。。。。字典里面不是只有Bc么

记忆有点模糊，应该是匹配的时候可以不考虑大小写

yevita 发表于 2017-11-14 12:18
记忆有点模糊，应该是匹配的时候可以不考虑大小写

好的 谢谢！！！

请问系楼主如果array是{“mn”}, 而name是“m”，output是[M]还是空？
问题就是“m”的substring只有“m”和“”。然后“m”是不是不算出现在了array中，只有“mn”才能算出现在了array中？

ARUI35 发表于 2017-11-18 05:47
请问系楼主如果array是{“mn”}, 而name是“m”，output是[M]还是空？
问题就是“m”的substring只有“m” ...

output是m，mn出现在array中，m找不到匹配