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

Commit553702e

Browse files
author
applewjg
committed
word ladder I && II
Change-Id: I3af4c30f73049d634bd4cc6fd0d0ac769f3d67dd
1 parentc05a6f1 commit553702e

File tree

2 files changed

+156
-0
lines changed

2 files changed

+156
-0
lines changed

‎WordLadder.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 20, 2014
4+
Problem: Word Ladder
5+
Difficulty: High
6+
Source: https://oj.leetcode.com/problems/word-ladder/
7+
Notes:
8+
Given two words (start and end), and a dictionary, find the length of shortest transformation
9+
sequence from start to end, such that:
10+
Only one letter can be changed at a time
11+
Each intermediate word must exist in the dictionary
12+
For example,
13+
Given:
14+
start = "hit"
15+
end = "cog"
16+
dict = ["hot","dot","dog","lot","log"]
17+
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
18+
return its length 5.
19+
Note:
20+
Return 0 if there is no such transformation sequence.
21+
All words have the same length.
22+
All words contain only lowercase alphabetic characters.
23+
24+
Solution: BFS.
25+
*/
26+
publicclassSolution {
27+
publicintladderLength(Stringstart,Stringend,Set<String>dict) {
28+
Queue<String>cur =newLinkedList<String>();
29+
if(start.compareTo(end) ==0)return0;
30+
cur.offer(start);
31+
intdepth =1;
32+
Set<String>visited =newHashSet<String>();
33+
while (cur.isEmpty() ==false) {
34+
Queue<String>queue =newLinkedList<String>();
35+
while(cur.isEmpty() ==false) {
36+
Stringstr =cur.poll();
37+
char[]word =str.toCharArray();
38+
for (inti =0;i <word.length; ++i) {
39+
charbefore =word[i];
40+
for (charch ='a';ch <='z'; ++ch) {
41+
word[i] =ch;
42+
Stringtemp =newString(word);
43+
if (end.compareTo(temp) ==0)returndepth +1;
44+
if (dict.contains(temp) ==true &&visited.contains(temp) ==false) {
45+
queue.offer(temp);
46+
visited.add(temp);
47+
}
48+
}
49+
word[i] =before;
50+
}
51+
}
52+
cur =queue;
53+
++depth;
54+
}
55+
return0;
56+
}
57+
}

‎WordLadderII.java

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 29, 2014
4+
Problem: Word Ladder II
5+
Difficulty: High
6+
Source: https://oj.leetcode.com/problems/word-ladder-ii/
7+
Notes:
8+
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
9+
Only one letter can be changed at a time
10+
Each intermediate word must exist in the dictionary
11+
For example,
12+
Given:
13+
start = "hit"
14+
end = "cog"
15+
dict = ["hot","dot","dog","lot","log"]
16+
Return
17+
[
18+
["hit","hot","dot","dog","cog"],
19+
["hit","hot","lot","log","cog"]
20+
]
21+
Note:
22+
All words have the same length.
23+
All words contain only lowercase alphabetic characters.
24+
25+
Solution: BFS + DFS
26+
*/
27+
28+
publicclassSolution {
29+
publicList<List<String>>findLadders(Stringstart,Stringend,Set<String>dict) {
30+
List<List<String>>res =newArrayList<List<String>>();
31+
if(start.compareTo(end) ==0)returnres;
32+
Set<String>visited =newHashSet<String>();
33+
Set<String>cur =newHashSet<String>();
34+
HashMap<String,ArrayList<String>>graph =newHashMap<String,ArrayList<String>>();
35+
graph.put(end,newArrayList<String>());
36+
cur.add(start);
37+
booleanfound =false;
38+
while (cur.isEmpty() ==false &&found ==false) {
39+
Set<String>queue =newHashSet<String>();
40+
for(Iterator<String>it=cur.iterator();it.hasNext();) {
41+
visited.add(it.next());
42+
}
43+
for(Iterator<String>it=cur.iterator();it.hasNext();) {
44+
Stringstr =it.next();
45+
char[]word =str.toCharArray();
46+
for (intj =0;j <word.length; ++j) {
47+
charbefore =word[j];
48+
for (charch ='a';ch <='z'; ++ch) {
49+
if (ch ==before)continue;
50+
word[j] =ch;
51+
Stringtemp =newString(word);
52+
if (dict.contains(temp) ==false)continue;
53+
if (found ==true &&end.compareTo(temp) !=0)continue;
54+
if (end.compareTo(temp) ==0) {
55+
found =true;
56+
(graph.get(end)).add(str);
57+
continue;
58+
}
59+
if (visited.contains(temp) ==false) {
60+
queue.add(temp);
61+
if (graph.containsKey(temp) ==false) {
62+
ArrayList<String>l =newArrayList<String>();
63+
l.add(str);
64+
graph.put(temp,l);
65+
}else {
66+
(graph.get(temp)).add(str);
67+
}
68+
}
69+
}
70+
word[j] =before;
71+
}
72+
}
73+
cur =queue;
74+
}
75+
if (found ==true) {
76+
ArrayList<String>path =newArrayList<String>();
77+
trace(res,graph,path,start,end);
78+
}
79+
returnres;
80+
}
81+
publicvoidtrace(List<List<String>>res,
82+
HashMap<String,ArrayList<String>>graph,
83+
ArrayList<String>path,
84+
Stringstart,Stringnow) {
85+
path.add(now);
86+
if (now.compareTo(start) ==0) {
87+
ArrayList<String>ans =newArrayList<String>(path);
88+
Collections.reverse(ans);
89+
res.add(ans);
90+
path.remove(path.size()-1);
91+
return;
92+
}
93+
ArrayList<String>cur =graph.get(now);
94+
for (inti =0;i <cur.size(); ++i) {
95+
trace(res,graph,path,start,cur.get(i));
96+
}
97+
path.remove(path.size()-1);
98+
}
99+
}

0 commit comments

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