Skip to content

Commit a36bbdb

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode solutions.
1 parent e8b6f28 commit a36bbdb

File tree

3 files changed

+247
-2
lines changed

3 files changed

+247
-2
lines changed

‎leetcode/472. Concatenated Words.md

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
## 472. Concatenated Words
2+
3+
### Question
4+
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
5+
6+
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
7+
8+
Example:
9+
10+
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
11+
12+
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
13+
14+
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
15+
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
16+
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
17+
18+
Note:
19+
1. The number of elements of the given array will not exceed 10,000
20+
2. The length sum of elements in the given array will not exceed 600,000.
21+
3. All the input string will only include lower case letters.
22+
4. The returned elements order does not matter.
23+
24+
### Solution
25+
* Method 1: dp
26+
* We need to sort the array first since we can only use short words to construct long words.
27+
* Use idea of [139. Word Break](https://leetcode.com/problems/word-break/description/) to check if we can use seen words to construct current word.
28+
* Finally add current word as a seen word.
29+
```Java
30+
class Solution {
31+
public List<String> findAllConcatenatedWordsInADict(String[] words) {
32+
List<String> result = new ArrayList<>();
33+
Arrays.sort(words, new Comparator<String>(){
34+
@Override
35+
public int compare(String a, String b){
36+
return a.length() - b.length();
37+
}
38+
});
39+
Set<String> checked = new HashSet<>();
40+
for(String word: words){
41+
if(canForm(word, checked)){
42+
result.add(word);
43+
}
44+
checked.add(word);
45+
}
46+
return result;
47+
}
48+
private boolean canForm(String word, Set<String> set){
49+
if(set.isEmpty()) return false;
50+
int len = word.length();
51+
boolean[] dp = new boolean[len + 1];
52+
dp[0] = true;
53+
LABEL:
54+
for(int i = 1; i <= len; i++){
55+
for(int j = 0; j < i; j++){
56+
if(set.contains(word.substring(j, i))){
57+
dp[i] |= dp[j];
58+
}
59+
if(dp[i]) break;
60+
}
61+
}
62+
return dp[len];
63+
}
64+
}
65+
```

‎leetcode/490. The Maze.md

Lines changed: 80 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -87,4 +87,83 @@ private static boolean searchBFS(int[][] maze, int[] start, int[] des, boolean[]
8787
}
8888
return false;
8989
}
90-
```
90+
```
91+
92+
### Amazon session
93+
* Method 1: dfs
94+
```Java
95+
class Solution {
96+
private static final int[][] dir = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
97+
private int[][] maze;
98+
private int[] destination;
99+
private Set<Integer> visited;
100+
private int height;
101+
private int width;
102+
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
103+
if(start[0] == destination[0] && start[1] == destination[1]) return true;
104+
this.maze = maze;
105+
if(maze == null || maze.length == 0) return true;
106+
this.destination = destination;
107+
visited = new HashSet<>();
108+
this.height = maze.length;
109+
this.width = maze[0].length;
110+
visited.add(start[0] * width + start[1]);
111+
for(int d = 0; d < 4; d++)
112+
if(dfs(start, d)) return true;
113+
return false;
114+
}
115+
private boolean dfs(int[] cur, int dir){
116+
for(int d = 0; d < 4; d++){
117+
if(dir == d || dir + d == 3) continue;
118+
int tx = cur[0], ty = cur[1];
119+
while(tx >= 0 && tx < height && ty >= 0 && ty < width && this.maze[tx][ty] == 0){
120+
tx += this.dir[d][0];
121+
ty += this.dir[d][1];
122+
}
123+
tx -= this.dir[d][0];
124+
ty -= this.dir[d][1];
125+
if(tx == destination[0] && ty == destination[1]) return true;
126+
if(!visited.contains(tx * width + ty)){
127+
visited.add(tx * width + ty);
128+
if(dfs(new int[]{tx, ty}, d)) return true;
129+
}
130+
}
131+
return false;
132+
}
133+
}
134+
```
135+
136+
* Method 2: bfs
137+
```Java
138+
class Solution {
139+
private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
140+
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
141+
if(maze == null || maze.length == 0) return true;
142+
if(start[0] == destination[0] && start[1] == destination[1]) return true;
143+
Queue<int[]> q = new LinkedList<>();
144+
Set<Integer> visited = new HashSet<>();
145+
int height = maze.length, width = maze[0].length;
146+
visited.add(start[0] * width + start[1]);
147+
q.offer(start);
148+
while(!q.isEmpty()){
149+
int[] cur = q.poll();
150+
if(cur[0] == destination[0] && cur[1] == destination[1]) return true;
151+
for(int d = 0; d < 4; d++){
152+
int[] next = findNext(cur, d, height, width, maze);
153+
if(visited.contains(next[0] * width + next[1])) continue;
154+
visited.add(next[0] * width + next[1]);
155+
q.offer(next);
156+
}
157+
}
158+
return false;
159+
}
160+
private int[] findNext(int[] cur, int d, int h, int w, int[][] maze){
161+
int tx = cur[0], ty = cur[1];
162+
while(tx >= 0 && tx < h && ty >= 0 && ty < w && maze[tx][ty] == 0){
163+
tx += dir[d][0];
164+
ty += dir[d][1];
165+
}
166+
return new int[]{tx - dir[d][0], ty - dir[d][1]};
167+
}
168+
}
169+
```

‎leetcode/505. The Maze II.md

Lines changed: 102 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@ There is a ball in a maze with empty spaces and walls. The ball can go through e
66
Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.
77

88
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
9+
910
```
1011
Example 1
1112
@@ -110,4 +111,104 @@ public class TheMazeII {
110111
shortestDistanceDFS(maze, new Node(row, col, l), des, path);
111112
}
112113
}
113-
```
114+
```
115+
116+
### Second time
117+
The idea of this question is graph traversal. Since we want to find the minimum path from start to destination, so we can use dp(or cache), to save duplicate visiting.
118+
Meanwhile, we need to use some ideas from the shortest path to update the path.
119+
* Method 1: bfs
120+
```Java
121+
class Solution {
122+
private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
123+
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
124+
if(maze == null || maze.length == 0 || (start[0] == destination[0] && start[1] == destination[1])) return 0;
125+
int height = maze.length, width = maze[0].length;
126+
int[][] dist = new int[height][width]; // records the temp minimum distance from start to current point
127+
for(int[] d : dist) Arrays.fill(d, Integer.MAX_VALUE);
128+
dist[start[0]][start[1]] = 0;
129+
Queue<int[]> q = new LinkedList<>();
130+
q.offer(start);
131+
int min = Integer.MAX_VALUE;
132+
while(!q.isEmpty()){
133+
int[] cur = q.poll();
134+
if(cur[0] == destination[0] && cur[1] == destination[1]){
135+
min = Math.min(min, dist[destination[0]][destination[1]]);
136+
continue;
137+
}
138+
for(int d = 0; d < 4; d++){
139+
int count = 0;
140+
int tx = cur[0], ty = cur[1];
141+
while(tx >= 0 && tx < height && ty >= 0 && ty < width && maze[tx][ty] == 0){
142+
count++;
143+
tx += dir[d][0];
144+
ty += dir[d][1];
145+
}
146+
count--;
147+
tx -= dir[d][0];
148+
ty -= dir[d][1];
149+
if(count + dist[cur[0]][cur[1]] < dist[tx][ty]){
150+
dist[tx][ty] = count + dist[cur[0]][cur[1]];
151+
if(dist[tx][ty] < min){
152+
q.offer(new int[]{tx, ty});
153+
}
154+
}
155+
}
156+
}
157+
return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1: min;
158+
}
159+
}
160+
```
161+
162+
* Method 2: dfs
163+
```Java
164+
class Solution {
165+
private int height;
166+
private int width;
167+
private int[][] dist;
168+
private int[] destination;
169+
private int[][] maze;
170+
private static final int[][] dir = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
171+
private int result = Integer.MAX_VALUE;
172+
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
173+
if(maze == null || maze.length == 0 || (start[0] == destination[0] && start[1] == destination[1])) return 0;
174+
this.maze = maze;
175+
this.height = maze.length;
176+
this.width = maze[0].length;
177+
this.dist = new int[height][width];
178+
this.destination = destination;
179+
for(int[] d : dist) Arrays.fill(d, Integer.MAX_VALUE);
180+
dist[start[0]][start[1]] = 0;
181+
for(int i = 0; i < 4; i++)
182+
dfs(start[0], start[1], i);
183+
return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ?
184+
-1: this.result;
185+
}
186+
private void dfs(int x, int y, int dir){
187+
if(x == destination[0] && y == destination[1]){
188+
this.result = Math.min(this.result, dist[destination[0]][destination[1]]);
189+
return;
190+
}else if(dist[x][y] < this.result){
191+
for(int d = 0; d < 4; d++){
192+
if(d == dir || d + dir == 3) continue;
193+
int count = 0;
194+
int tx = x, ty = y;
195+
while(tx >= 0 && tx < height && ty >= 0 && ty < width && maze[tx][ty] == 0){
196+
count++;
197+
tx += Solution.dir[d][0];
198+
ty += Solution.dir[d][1];
199+
}
200+
count--;
201+
tx -= Solution.dir[d][0];
202+
ty -= Solution.dir[d][1];
203+
if(count + dist[x][y] < dist[tx][ty]){
204+
dist[tx][ty] = count + dist[x][y];
205+
dfs(tx, ty, d);
206+
}
207+
}
208+
}
209+
}
210+
}
211+
```
212+
213+
### Reference
214+
1. [Java 6ms BFS by optimizing solution #2](https://leetcode.com/problems/the-maze-ii/discuss/290079/Java-6ms-BFS-by-optimizing-solution-2)

0 commit comments

Comments
 (0)