Google电面, 求人品

laiguojiuhao 发表于 2017-1-13 10:07

可以说一下大概思路吗？

bigbearlake 发表于 2017-1-18 02:04
可以说一下大概思路吗？

就是建个trie暴力搜的；如果这个词的当前字母不匹配，就检查‘*’在不在：不在返回错，否则用'*'依次替代1～len(rest of word)长度的字母继续搜

可不可以每次考虑用*和不用*， 用*的话，26个试一边，不用*的话，直接跳到下个比较，？

bbmbill 发表于 2017-1-13 09:14
这道题能不能把每个trie node的子节点加一个‘*’的情况，指向node自己，然后dfs?这样follow up的问题应该 ...

你好，好像你这样解决不了比如 fo*d, fodddd这样的case

您好！
本帖隐藏的内容需要积分高于 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

写个java版本的吧, 楼主上面的例子应该都能过:

1. public class FilteredTrie {
   
2.     static class TrieNode{
   
3.         char ch;
   
4.         boolean hasStar= false;
   
5.         boolean isEnd= false;
   
6.         TrieNode[] children= new TrieNode[26];
   
7.         public TrieNode(char ch){
   
8.             this.ch= ch;
   
9.         }
   
10. 
    
11.         @Override
    
12.         public String toString(){
    
13.             return this.ch+" hasStar:"+ hasStar+ "  isEnd:"+ isEnd;
    
14.         }
    
15.     }
    
16.     static class Trie{
    
17.         TrieNode root= new TrieNode('*');
    
18.         public Trie(String[] words){
    
19.             for(String word: words){
    
20.                 TrieNode node= root;
    
21.                 for(int i=0; i<word.length(); i++){
    
22.                     char ch= word.charAt(i);
    
23.                     if(ch=='*'){
    
24.                         node.hasStar= true;
    
25.                         continue;
    
26.                     }
    
27.                     if(node.children[ch-'a']==null){
    
28.                         node.children[ch-'a']= new TrieNode(ch);
    
29.                     }
    
30.                     node= node.children[ch-'a'];
    
31.                 }
    
32.                 node.isEnd= true;
    
33.             }
    
34.         }
    
35.         public boolean search(String word){
    
36.             return search(word, root);
    
37.         }
    
38.         public boolean search(String word, TrieNode _node){
    
39.             if(word.length()==0) return _node.isEnd;
    
40.             TrieNode node= _node;
    
41.             for(int i=0; i<word.length(); i++){
    
42.                 char ch= word.charAt(i);
    
43.                 if(node.hasStar){
    
44.                     for(int len=0; i+len<=word.length(); i++){
    
45.                         node.hasStar= false;
    
46.                         if(search(word.substring(i+len), node)){
    
47.                             node.hasStar= true;
    
48.                             return true;
    
49.                         }
    
50.                         node.hasStar= true;
    
51.                     }
    
52.                     return false;
    
53.                 }else{
    
54.                     if(node.children[ch-'a']==null)  return false;
    
55.                     node= node.children[ch-'a'];
    
56.                 }
    
57.             }
    
58.             return node.isEnd;
    
59.         }
    
60.     }
    
61.     public static void main(String[] args){
    
62.         String[] filters= new String[]{"h*o", "fo*d", "fo*de"};
    
63.         Trie trie= new Trie(filters);
    
64.         String[] words= new String[]{"food", "hello", "foo", "fod", "foood", "focfd", "fodede"};
    
65.         for(String word: words){
    
66.             System.out.println(trie.search(word));
    
67.         }
    
68.     }
    
69. }

复制代码