Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite02af9c

Browse files
committed
dp
1 parenta1a7a65 commite02af9c

File tree

2 files changed

+171
-19
lines changed

2 files changed

+171
-19
lines changed

‎dfs/Exist.java

Lines changed: 80 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
packageAlgorithms.dfs;
22

33
publicclassExist {
4-
publicbooleanexist(char[][]board,Stringword) {
4+
publicbooleanexist1(char[][]board,Stringword) {
55
if (board ==null ||word ==null
66
||board.length ==0 ||board[0].length ==0) {
77
returnfalse;
@@ -16,7 +16,7 @@ public boolean exist(char[][] board, String word) {
1616
for (inti =0;i <rows;i++) {
1717
for (intj =0;j <cols;j++) {
1818
// dfs all the characters in the matrix
19-
if (dfs(board,i,j,word,0,visit)) {
19+
if (dfs1(board,i,j,word,0,visit)) {
2020
returntrue;
2121
}
2222
}
@@ -25,7 +25,7 @@ public boolean exist(char[][] board, String word) {
2525
returnfalse;
2626
}
2727

28-
publicbooleandfs(char[][]board,inti,intj,Stringword,intwordIndex,boolean[][]visit) {
28+
publicbooleandfs1(char[][]board,inti,intj,Stringword,intwordIndex,boolean[][]visit) {
2929
introws =board.length;
3030
intcols =board[0].length;
3131

@@ -53,27 +53,100 @@ public boolean dfs(char[][] board, int i, int j, String word, int wordIndex, boo
5353

5454
// 递归
5555
// move down
56-
if (dfs(board,i +1,j,word,wordIndex +1,visit)) {
56+
if (dfs1(board,i +1,j,word,wordIndex +1,visit)) {
5757
returntrue;
5858
}
5959

6060
// move up
61-
if (dfs(board,i -1,j,word,wordIndex +1,visit)) {
61+
if (dfs1(board,i -1,j,word,wordIndex +1,visit)) {
6262
returntrue;
6363
}
6464

6565
// move right
66-
if (dfs(board,i,j +1,word,wordIndex +1,visit)) {
66+
if (dfs1(board,i,j +1,word,wordIndex +1,visit)) {
6767
returntrue;
6868
}
6969

7070
// move left
71-
if (dfs(board,i,j -1,word,wordIndex +1,visit)) {
71+
if (dfs1(board,i,j -1,word,wordIndex +1,visit)) {
7272
returntrue;
7373
}
7474

7575
// 回溯
7676
visit[i][j] =false;
7777
returnfalse;
7878
}
79+
80+
/*
81+
* Solution 2: 可以省掉一个visit的数组
82+
* */
83+
publicbooleanexist(char[][]board,Stringword) {
84+
if (board ==null ||word ==null
85+
||board.length ==0 ||board[0].length ==0) {
86+
returnfalse;
87+
}
88+
89+
introws =board.length;
90+
intcols =board[0].length;
91+
92+
// i means the index.
93+
for (inti =0;i <rows;i++) {
94+
for (intj =0;j <cols;j++) {
95+
// dfs all the characters in the matrix
96+
if (dfs(board,i,j,word,0)) {
97+
returntrue;
98+
}
99+
}
100+
}
101+
102+
returnfalse;
103+
}
104+
105+
publicbooleandfs(char[][]board,inti,intj,Stringword,intwordIndex) {
106+
introws =board.length;
107+
intcols =board[0].length;
108+
109+
intlen =word.length();
110+
if (wordIndex >=len) {
111+
returntrue;
112+
}
113+
114+
// the index is out of bound.
115+
if (i <0 ||i >=rows ||j <0 ||j >=cols) {
116+
returnfalse;
117+
}
118+
119+
// the character is wrong.
120+
if (word.charAt(wordIndex) !=board[i][j]) {
121+
returnfalse;
122+
}
123+
124+
// mark it to be '#', so we will not revisit this.
125+
board[i][j] ='#';
126+
127+
// 递归
128+
// move down
129+
if (dfs(board,i +1,j,word,wordIndex +1)) {
130+
returntrue;
131+
}
132+
133+
// move up
134+
if (dfs(board,i -1,j,word,wordIndex +1)) {
135+
returntrue;
136+
}
137+
138+
// move right
139+
if (dfs(board,i,j +1,word,wordIndex +1)) {
140+
returntrue;
141+
}
142+
143+
// move left
144+
if (dfs(board,i,j -1,word,wordIndex +1)) {
145+
returntrue;
146+
}
147+
148+
// 回溯
149+
board[i][j] =word.charAt(wordIndex);
150+
returnfalse;
151+
}
79152
}

‎dp/WordBreak2.java

Lines changed: 91 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,7 @@ public static void main(String[] strs) {
3939
Algorithms.permutation.Stopwatchtimer1 =newAlgorithms.permutation.Stopwatch();
4040

4141
// 递归模板，加剪枝
42-
wordBreak(s,dict);
42+
wordBreak2(s,dict);
4343

4444
System.out
4545
.println("Computing time with DFS2: "
@@ -55,6 +55,13 @@ public static void main(String[] strs) {
5555
.println("Computing time with DFS3: "
5656
+timer3.elapsedTime() +" millisec.");
5757

58+
// DP + DFS
59+
wordBreak4(s,dict);
60+
61+
System.out
62+
.println("Computing time with DFS4: "
63+
+timer3.elapsedTime() +" millisec.");
64+
5865
//System.out.println(list.toString());
5966
}
6067

@@ -92,10 +99,6 @@ public static List<String> dfs(String s, Set<String> dict, HashMap<String, List<
9299
// 字符串划分为2边，计算右边的word break.
93100
List<String>listRight =dfs(s.substring(i,len),dict,map);
94101

95-
// 右边不能break的时候，我们跳过.
96-
if (listRight.size() ==0) {
97-
continue;
98-
}
99102

100103
// 把左字符串加到右字符串中，形成新的解.
101104
for (Stringr:listRight) {
@@ -120,7 +123,7 @@ public static List<String> dfs(String s, Set<String> dict, HashMap<String, List<
120123
*/
121124

122125
// 我们用DFS来解决这个问题吧
123-
publicstaticList<String>wordBreak(Strings,Set<String>dict) {
126+
publicstaticList<String>wordBreak2(Strings,Set<String>dict) {
124127
if (s ==null ||s.length() ==0 ||dict ==null) {
125128
returnnull;
126129
}
@@ -257,25 +260,101 @@ public static void dfs3(String s, Set<String> dict,
257260
return;
258261
}
259262

263+
// cut branch.
264+
intbeforeChange =ret.size();
260265
for (inti =index;i <len;i++) {
261266
// 注意这些索引的取值。左字符串的长度从0到len
262267
Stringleft =s.substring(index,i +1);
263-
if (!dict.contains(left) || !canBreak[i +1]) {
268+
if (!dict.contains(left)) {
264269
// 如果左字符串不在字典中，不需要继续递归
265270
continue;
266271
}
267272

268273
// if can't find any solution, return false, other set it
269274
// to be true;
270275
path.add(left);
271-
272-
intbeforeChange =ret.size();
273276
dfs3(s,dict,path,ret,i +1,canBreak);
274-
// 注意这些剪枝的代码. 关键在于此以减少复杂度
275-
if (ret.size() ==beforeChange) {
276-
canBreak[i +1] =false;
277+
278+
path.remove(path.size() -1);
279+
}
280+
281+
// 注意这些剪枝的代码. 关键在于此以减少复杂度
282+
if (ret.size() ==beforeChange) {
283+
canBreak[index] =false;
284+
}
285+
}
286+
287+
/*
288+
// 解法4：先用DP来求解，然后再做
289+
*/
290+
// 我们用DFS来解决这个问题吧
291+
publicstaticList<String>wordBreak4(Strings,Set<String>dict) {
292+
if (s ==null ||s.length() ==0 ||dict ==null) {
293+
returnnull;
294+
}
295+
296+
List<String>ret =newArrayList<String>();
297+
298+
List<String>path =newArrayList<String>();
299+
300+
intlen =s.length();
301+
302+
// i: 表示从i索引开始的字串可以word break.
303+
boolean[]D =newboolean[len +1];
304+
D[len] =true;
305+
for (inti =len -1;i >=0;i--) {
306+
for (intj =i;j <=len -1;j++) {
307+
// 左边从i 到 j
308+
D[i] =false;
309+
if (D[j +1] &&dict.contains(s.substring(i,j +1))) {
310+
D[i] =true;
311+
break;
312+
}
277313
}
314+
}
315+
316+
dfs4(s,dict,path,ret,0,D);
317+
318+
returnret;
319+
}
320+
321+
// 我们用DFS模板来解决这个问题吧
322+
publicstaticvoiddfs4(Strings,Set<String>dict,
323+
List<String>path,List<String>ret,intindex,
324+
booleancanBreak[]) {
325+
intlen =s.length();
326+
if (index ==len) {
327+
// 结束了。index到了末尾
328+
StringBuildersb =newStringBuilder();
329+
for (Stringstr:path) {
330+
sb.append(str);
331+
sb.append(" ");
332+
}
333+
// remove the last " "
334+
sb.deleteCharAt(sb.length() -1);
335+
ret.add(sb.toString());
336+
return;
337+
}
338+
339+
// if can't break, we exit directly.
340+
if (!canBreak[index]) {
341+
return;
342+
}
343+
344+
for (inti =index;i <len;i++) {
345+
// 注意这些索引的取值。左字符串的长度从0到len
346+
Stringleft =s.substring(index,i +1);
347+
if (!dict.contains(left)) {
348+
// 如果左字符串不在字典中，不需要继续递归
349+
continue;
350+
}
351+
352+
// if can't find any solution, return false, other set it
353+
// to be true;
354+
path.add(left);
355+
dfs4(s,dict,path,ret,i +1,canBreak);
278356
path.remove(path.size() -1);
279357
}
358+
280359
}
281360
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp