脸书家onsite

贴我的代码，我这儿'*'是match 0个或多个前缀字符的 '*' Matches zero or more of the preceding element

1. public class WordDictionary {
   
2.     TrieNode root;
   
3.     WordDictionary() {
   
4.         root = new TrieNode();
   
5.     }
   
6.     // Adds a word into the data structure.
   
7.     public void addWord(String word) {
   
8.         TrieNode cur = root;
   
9.         for(int i=0; i<word.length(); i++) {
   
10.             char c = word.charAt(i);
    
11.             int index = c - 'a';
    
12.             if(cur.children[index] == null) {
    
13.                 cur.children[index] = new TrieNode();
    
14.             }
    
15.             cur = cur.children[index];
    
16.             cur.letter = c;
    
17.         }
    
18.         cur.hasWord = true;
    
19.     }
    
20. 
    
21.     public boolean search(String word) {
    
22.         TrieNode cur = root;
    
23.         return search(root, word, 0);
    
24.     }
    
25.    
    
26.     private boolean search(TrieNode cur, String word, int index) {
    
27.         if(cur == null) {
    
28.             return false;
    
29.         }
    
30.         if(index == word.length()) {
    
31.             return cur.hasWord;
    
32.         }
    
33.         char c = word.charAt(index);
    
34.         if(index == word.length() - 1 || word.charAt(index+1) != '*') {
    
35.             if(c == '.') {
    
36.                 for(TrieNode node : cur.children) {
    
37.                     if(search(node, word, index+1)) {
    
38.                         return true;
    
39.                     }
    
40.                 }
    
41.                 return false;
    
42.             } else if(c == '*') {
    
43.                 return false;
    
44.             } else {
    
45.                 return search(cur.children[c - 'a'], word, index+1);
    
46.             }
    
47.         } else {
    
48.             if(search(cur, word, index+2)) {
    
49.                 return true;
    
50.             }
    
51.             if(c == '.') {
    
52.                 for(TrieNode node : cur.children) {
    
53.                     if(search(node, word, index)) {
    
54.                         return true;
    
55.                     }
    
56.                 }
    
57.                 return false;
    
58.             } else {
    
59.                 return search(cur.children[c - 'a'], word, index);
    
60.             }
    
61.         }
    
62. 
    
63.     }
    
64.    
    
65.     class TrieNode {
    
66.         TrieNode[] children;
    
67.         char letter;
    
68.         boolean hasWord;
    
69.         TrieNode() {
    
70.             children = new TrieNode[26];
    
71.             hasWord = false;
    
72.         }
    
73.     }
    
74. }

复制代码

liurudahai 发表于 2016-9-29 00:44
不对，应该是这样，分两种情况，因为他可以匹配0个字符，所以直接可以用*后面那个字符在当前层搜索，如果 ...

这个应该是对当前层所有的descendants递归吧，不光是children. 因为*可匹配任意长度。例如字典只有"abcd", 搜索“a*d". 在匹配a之后，其所有子孙树：“bcd", "cd", "d"都要和*之后的“d"比较才不会误漏字典的词。当然也许我误解你具体如何实现的，若有请见谅。

多谢楼主！

zzgzzm 发表于 2016-11-6 10:50
这个应该是FB的经典高频题了，地里有很多面经。就是先让自己设计一个class Vec表示欧式空间的N维向量v =  ...

binary search vs two pointers，binary search怎么用来解决dot product？可以细说一下吗？之前我就是感觉two pointers和hashmap。

knight0clk 发表于 2016-11-6 23:11
binary search vs two pointers，binary search怎么用来解决dot product？可以细说一下吗？之前我就是感 ...

这实际上就是在于怎么求2个sorted arrays 的所有相交元素。对每个长array 的元素在短array 中binary search. 注意每次若未找到match 的话一定要记录当前最接近的index. 不要每次都从头binary search.

zzgzzm 发表于 2016-11-7 00:06
这实际上就是在于怎么求2个sorted arrays 的所有相交元素。对每个长array 的元素在短array 中binary sear ...

大哥你厉害，我懂了，多谢！最坏的复杂度nlogm，貌似也可以接受。

zzgzzm 发表于 2016-11-6 10:50
这个应该是FB的经典高频题了，地里有很多面经。就是先让自己设计一个class Vec表示欧式空间的N维向量v =  ...

Got it! thanks!  

zzgzzm 发表于 2016-11-6 12:56
这个应该就是LC211的扩展了，加上了support for '*'. 关键是当search word遇到'*'，要跳过所有可能连续的 ...

你这个假设是'*'可以替代任何character. 但是如果是替代previous character就不行了

fubu 发表于 2016-11-6 13:36
贴我的代码，我这儿'*'是match 0个或多个前缀字符的 '*' Matches zero or more of the preceding element[/ ...

if(search(cur, word, index+2)) {
                return true;
            }
怎么直接返回true了？ 'abc'也可以进入这个，但是不应该返回true吧

liurudahai 发表于 2016-9-29 00:44
不对，应该是这样，分两种情况，因为他可以匹配0个字符，所以直接可以用*后面那个字符在当前层搜索，如果 ...

我觉得只有当*前面是一个'.'的情况才需要对所有children遍历吧, 如果是一个普通字符, 就遍历那个字符对应的children就好.