Skip to content

Commit dbf2b20

Browse files
fishercoder1534fishercoder1534
committed
add 576
1 parent 20fff9d commit dbf2b20

File tree

4 files changed

+110
-2
lines changed

4 files changed

+110
-2
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ Your ideas/fixes/algorithms are more than welcome!
4343
|583|[Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_583.java) | O(m*n) |O(m*n) could be optimized to O(n) | Medium | DP
4444
|582|[Kill Process](https://leetcode.com/problems/kill-process/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_582.java) | O(n) |O(h) | Medium | Stack
4545
|581|[Shortest Unsorted Continuous Subarray](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_581.java) | O(n) |O(1) | Easy | Array, Sort
46+
|576|[Out of Boundary Paths](https://leetcode.com/problems/out-of-boundary-paths/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_576.java) | O(N*m*n) |O(m*n) | Hard | DP, DFS
4647
|575|[Distribute Candies](https://leetcode.com/problems/distribute-candies/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_575.java) | O(nlogn) |O(1) | Easy | Array
4748
|573|[Squirrel Simulation](https://leetcode.com/problems/squirrel-simulation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_573.java) | O(n) |O(1) | Medium | Math
4849
|572|[Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_572.java) | O(m*n) |O(1) | Easy | Tree

‎src/main/java/com/fishercoder/solutions/_126.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* 126. Word Ladder II
8+
*
9+
* Given two words (beginWord and endWord), and a dictionary's word list,
10+
* find all shortest transformation sequence(s) from beginWord to endWord, such that:
11+
12+
Only one letter can be changed at a time
13+
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
14+
15+
For example,
16+
Given:
17+
beginWord = "hit"
18+
endWord = "cog"
19+
wordList = ["hot","dot","dog","lot","log","cog"]
20+
21+
Return
22+
[
23+
["hit","hot","dot","dog","cog"],
24+
["hit","hot","lot","log","cog"]
25+
]
26+
27+
Note:
28+
Return an empty list if there is no such transformation sequence.
29+
All words have the same length.
30+
All words contain only lowercase alphabetic characters.
31+
You may assume no duplicates in the word list.
32+
You may assume beginWord and endWord are non-empty and are not the same.
33+
*/
34+
public class _126 {
35+
36+
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
37+
List<List<String>> result = new ArrayList<>();
38+
return result;
39+
}
40+
41+
}

‎src/main/java/com/fishercoder/solutions/_127.java

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,9 @@
77
/**
88
* 127. Word Ladder
99
*
10-
* Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
10+
* Given two words (beginWord and endWord),
11+
* and a dictionary's word list,
12+
* find the length of shortest transformation sequence from beginWord to endWord, such that:
1113
1214
Only one letter can be changed at a time.
1315
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
@@ -33,7 +35,7 @@
3335
*/
3436
public class _127 {
3537

36-
/**Credit: https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms/16*/
38+
/**reference: https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms/16*/
3739
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
3840
Set<String> dict = new HashSet<>(wordList);
3941
Set<String> startSet = new HashSet<>();

‎src/main/java/com/fishercoder/solutions/_576.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 576. Out of Boundary Paths
5+
*
6+
* There is an m by n grid with a ball.
7+
* Given the start coordinate (i,j) of the ball,
8+
* you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right).
9+
* However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary.
10+
* The answer may be very large, return it after mod 109 + 7.
11+
12+
Example 1:
13+
14+
Input:m = 2, n = 2, N = 2, i = 0, j = 0
15+
Output: 6
16+
Explanation:
17+
18+
Example 2:
19+
20+
Input:m = 1, n = 3, N = 3, i = 0, j = 1
21+
Output: 12
22+
Explanation:
23+
24+
Note:
25+
26+
Once you move the ball out of boundary, you cannot move it back.
27+
The length and height of the grid is in range [1,50].
28+
N is in range [0,50].
29+
30+
*/
31+
public class _576 {
32+
33+
/**reference: https://leetcode.com/articles/out-of-boundary-paths/#approach-2-recursion-with-memoization-accepted*/
34+
public int findPaths(int m, int n, int N, int x, int y) {
35+
int M = 1000000000 + 7;
36+
int dp[][] = new int[m][n];
37+
dp[x][y] = 1;
38+
int count = 0;
39+
for (int moves = 1; moves <= N; moves++) {
40+
int[][] temp = new int[m][n];
41+
for (int i = 0; i < m; i++) {
42+
for (int j = 0; j < n; j++) {
43+
if (i == m - 1) {
44+
count = (count + dp[i][j]) % M;
45+
}
46+
if (j == n - 1) {
47+
count = (count + dp[i][j]) % M;
48+
}
49+
if (i == 0) {
50+
count = (count + dp[i][j]) % M;
51+
}
52+
if (j == 0) {
53+
count = (count + dp[i][j]) % M;
54+
}
55+
temp[i][j] = (((i > 0 ? dp[i - 1][j] : 0) + (i < m - 1 ? dp[i + 1][j] : 0)) % M +
56+
((j > 0 ? dp[i][j - 1] : 0) + (j < n - 1 ? dp[i][j + 1] : 0)) % M) % M;
57+
}
58+
}
59+
dp = temp;
60+
}
61+
return count;
62+
}
63+
64+
}

0 commit comments

Comments
 (0)