Skip to content

Commit ac147c9

Browse files
awangdevawangdev
committed
word search II, TrieNode - boolean visited
1 parent 904ba02 commit ac147c9

File tree

5 files changed

+646
-460
lines changed

5 files changed

+646
-460
lines changed

‎Java/HashWithCustomizedClass(LinkedList).java

Lines changed: 167 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,167 @@
1+
M
2+
3+
练习HashMap with customized class.
4+
5+
```
6+
/*
7+
Build Hashtable datastructure with three methods: set, get, getrandom.
8+
9+
Note1: getrandom needs to pick evenly/uniformaly distributed entry.
10+
11+
Note2: to be realistic, hashtable should be able to handle collision, that's where linkedlist comes into play.
12+
13+
Note3: use default object.hashcode() function to get hash code, then apply hashcode % table size
14+
15+
16+
More about O(1) random access
17+
If no collision, uniform random access is easy.
18+
19+
With collision, need to figure our how to access element on the linkedlist with O(1), but it's unlikely.
20+
So, like Java HashMap, we can implement rehashing. Bascially, when map size increase to over capacity, double the capacity.
21+
22+
*/
23+
24+
import java.io.*;
25+
import java.util.*;
26+
27+
public class CHashMap<K, V> {
28+
public int capacity;
29+
public int count;
30+
public Entry<K,V>[] table;
31+
32+
public class Entry<K, V> {
33+
public V value;
34+
public K key;
35+
public Entry<K,V> next;
36+
37+
public Entry(K key, V value, Entry<K,V> next) {
38+
this.value = value;
39+
this.key = key;
40+
this.next = next;
41+
}
42+
}
43+
44+
45+
public CHashMap() {
46+
this.capacity = 16;
47+
this.table = new Entry[this.capacity];
48+
this.count = 0;
49+
}
50+
51+
public CHashMap(int capacity) {
52+
this.capacity = capacity;
53+
this.table = new Entry[this.capacity];
54+
this.count = 0;
55+
}
56+
57+
public V get(K key) {
58+
if (key == null) {
59+
return null;
60+
}
61+
int hashedKey = hashFunction(key);
62+
if (table[hashedKey] != null) {
63+
Entry<K,V> node = table[hashedKey];
64+
while (node != null) {
65+
if (node.key.equals(key)) {
66+
return node.value;
67+
}
68+
node = node.next;
69+
}
70+
}
71+
return null;
72+
}
73+
74+
75+
public void put(K key, V value) {
76+
if (key == null) {
77+
return;
78+
}
79+
this.count++;
80+
Entry<K,V> entry = new Entry<K,V>(key, value, null);
81+
int hashedKey = hashFunction(key);
82+
if (table[hashedKey] == null) {
83+
table[hashedKey] = entry;
84+
} else {
85+
Entry<K,V> node = table[hashedKey];
86+
if (node.key.equals(key)) {
87+
table[hashedKey] = entry;
88+
entry.next = node.next;
89+
return;
90+
}
91+
while (node.next != null) {
92+
if (node.next.key.equals(key)) {
93+
Entry<K,V> temp = node.next;
94+
node.next = entry;
95+
entry.next = temp.next;
96+
return;
97+
}
98+
node = node.next;
99+
}
100+
node.next = entry;
101+
}
102+
}
103+
104+
public int hashFunction (K key) {
105+
return Math.abs(key.hashCode()) % this.capacity;
106+
}
107+
108+
public void display() {
109+
for (int i = 0; i < table.length; i++) {
110+
Entry<K,V> node = table[i];
111+
StringBuffer sb = new StringBuffer();
112+
while (node != null) {
113+
sb.append("[key: " + node.key + ", value: " + node.value + "], ");
114+
node = node.next;
115+
}
116+
if (sb.length() != 0)
117+
System.out.println(sb.toString());
118+
}
119+
System.out.println();
120+
}
121+
122+
/*
123+
If no collision, uniform random access is easy.
124+
125+
With collision, need to figure our how to access element on the linkedlist with O(1), but it's unlikely.
126+
127+
*/
128+
public V getRandom() {
129+
Random rd = new Random();
130+
int hashedKey = hashFunction(rd.nextInt(this.capacity));
131+
return table[hashedKey];
132+
}
133+
134+
135+
136+
137+
138+
139+
public static void main(String[] args) {
140+
CHashMap<Character, String> map = new CHashMap<Character, String>(2);
141+
142+
System.out.println("TEST SET------");
143+
map.put('a', "1st string");
144+
map.put('b', "2nd string!");
145+
map.display();
146+
map.put('a', "wowo change");
147+
map.display();
148+
149+
150+
System.out.println("TEST PUT------");
151+
System.out.println(map.get('a'));
152+
System.out.println(map.get('c'));
153+
map.put('c', "okay test c");
154+
System.out.println(map.get('c'));
155+
map.display();
156+
157+
System.out.println("TEST COLLISION------");
158+
map.put('d', "test d");
159+
map.put('e', "test E");
160+
map.display();
161+
162+
163+
//test getrandom
164+
165+
}
166+
}
167+
```

‎Java/Word Search II.java

Lines changed: 43 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,9 @@
11
H
22

3+
Big improvement: use boolean visited on TrieNode!
4+
不要用rst.contains(...), 因为这个是O(n) 在leetcode还是会timeout（lintcode竟然可以pass）!
5+
在Trie search() method 里面，凡是visit过的，mark一下。
6+
37
Regular:
48
for loop on words: inside, do board DFS based on each word.
59
Time cpmplexity: word[].length * boardWidth * boardHeight * (4^wordMaxLength)
@@ -84,70 +88,71 @@
8488
node.subtree.get(current).isString: this determines if a string exists or not.
8589
*/
8690

91+
/*NOTE: is boolean visited on Trie!!! */
8792
public class Solution {
8893
class TrieNode {
8994
String str;
9095
boolean isEnd;
96+
boolean visited;
9197
HashMap<Character, TrieNode> children;
9298
public TrieNode () {
9399
this.isEnd = false;
100+
this.visited = false;
94101
this.str = "";
95102
children = new HashMap<Character, TrieNode>();
96103
}
97104
}
98105
public TrieNode root;
99-
public int[] xd = {1, -1, 0, 0};
100-
public int[] yd = {0, 0, 1, -1};
101106

102-
public ArrayList<String> wordSearchII(char[][] board, ArrayList<String> words) {
103-
ArrayList<String> rst = new ArrayList<String>();
107+
public List<String> findWords(char[][] board, String[] words) {
108+
List<String> rst = new ArrayList<String>();
104109
if (board == null || board.length == 0 || board[0].length == 0
105-
|| words == null || words.size() == 0) {
110+
|| words == null || words.length == 0) {
106111
return rst;
107112
}
108113

109114
//Build Trie with words
110115
root = new TrieNode();
111-
for (int i = 0; i < words.size(); i++) {
112-
insert(words.get(i));
116+
for (int i = 0; i < words.length; i++) {
117+
insert(words[i]);
113118
}
114119

115120
//Validate existance of the words in board
121+
boolean[][] visited = new boolean[board.length][board[0].length];
116122
for (int i = 0; i < board.length; i++) {
117123
for (int j = 0; j < board[0].length; j++) {
118-
dfs(board, i, j, rst, "");
124+
dfs(rst, "", i, j, visited, board);
119125
}
120126
}
121127

122128
return rst;
123129
}
124130

125131
//4 direction DFS search
126-
public void dfs(char[][] board, int x, int y, ArrayList<String> rst, String s) {
127-
if (x < 0 || x >= board.length || y < 0 || y >= board[x].length) {
128-
return;
129-
}
130-
if (board[x][y] == '#') {
131-
return;
132-
}
133-
s += board[x][y];
134-
135-
if (!startWith(s)) {
136-
return;
137-
}
138-
if (search(s) && !rst.contains(s)) {
139-
rst.add(s);
140-
}
141-
142-
char temp = board[x][y];
143-
board[x][y] = '#';
144-
for (int i = 0; i < 4; i++) {
145-
int nX = x + xd[i];
146-
int nY = y + yd[i];
147-
dfs(board, nX, nY, rst, s);
148-
}
149-
board[x][y] = temp;
150-
132+
public void dfs(List<String> rst, String s, int x, int y, boolean[][] visited, char[][] board) {
133+
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
134+
return;
135+
}
136+
if (visited[x][y]) {
137+
return;
138+
}
139+
s += board[x][y];
140+
if (!startWith(s)) {
141+
return;
142+
}
143+
144+
if (search(s)) {
145+
rst.add(s);
146+
}
147+
int[] dx = {0,0,1,-1};
148+
int[] dy = {1,-1,0,0};
149+
visited[x][y] = true;
150+
for (int i = 0; i < 4; i++) {
151+
int nx = x + dx[i];
152+
int ny = y + dy[i];
153+
dfs(rst, s, nx, ny, visited, board);
154+
}
155+
visited[x][y] = false;
151156
}
152157

153158
/**************************Trie section *********************/
@@ -177,7 +182,11 @@ public boolean search(String s) {
177182
}
178183
node = node.children.get(c);
179184
}
180-
return node.isEnd;
185+
if (node.visited || !node.isEnd) {
186+
return false;
187+
}
188+
node.visited = true;
189+
return true;
181190
}
182191

183192
public boolean startWith(String s) {
@@ -203,7 +212,6 @@ public boolean startWith(String s) {
203212

204213

205214

206-
207215
/*
208216
Attempt1:
209217
Thoughts:

0 commit comments

Comments
 (0)