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

Commit1d768be

Browse files
committed
127 (3) add two-end BFS solution, cool!
1 parent992f302 commit1d768be

File tree

5 files changed

+1994
-33
lines changed

5 files changed

+1994
-33
lines changed

‎src/_127_WordLadder/Solution.java

Lines changed: 34 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -21,53 +21,58 @@
2121
*
2222
*******************************************************************************
2323
* {@link https://leetcode.com/problems/word-ladder/ }
24-
* -------------------------------------------------------------
25-
* 1. use StringBuilder for repeated string operations
26-
* 2. loop over 'a' - 'z': for (char ch = 'a'; ch <= 'z'; ch++)
24+
* @reference {@link https://leetcode.com/discuss/28573/share-my-two-end-bfs-in-c-80ms }
2725
*/
2826
package_127_WordLadder;
2927

3028
importjava.util.HashSet;
3129
importjava.util.Set;
3230

3331
/** see test {@link _127_WordLadder.SolutionTest } */
32+
// two-end BFS, construct graph from begin and end at the same time
3433
publicclassSolution {
35-
publicintladderLength(StringbeginWord,StringendWord,
36-
Set<String>wordDict) {
37-
if (beginWord.equals(endWord)) {
38-
return2;
39-
}
34+
35+
publicintladderLength(StringbeginWord,StringendWord,Set<String>wordDict) {
36+
intlen =1;
37+
Set<String>beginSet =newHashSet<>();
38+
Set<String>endSet =newHashSet<>();
4039
Set<String>visited =newHashSet<>();
41-
Set<String>current =newHashSet<>();
42-
current.add(beginWord);
40+
beginSet.add(beginWord);
41+
endSet.add(endWord);
4342
visited.add(beginWord);
44-
45-
intwordsInLadder =1;
46-
intwordLen =beginWord.length();
47-
while (!current.isEmpty()) {
43+
visited.add(endWord);
44+
45+
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
46+
// add new words to smaller set to achieve better performance
47+
booleanisBeginSetSmall =beginSet.size() <endSet.size();
48+
Set<String>small =isBeginSetSmall ?beginSet :endSet;
49+
Set<String>big =isBeginSetSmall ?endSet :beginSet;
4850
Set<String>next =newHashSet<>();
49-
wordsInLadder++;
50-
// traverse current level
51-
for (Stringstr :current) {
52-
for (inti =0;i <wordLen;i++) {
53-
StringBuilderstrBuilder =newStringBuilder(str);
51+
len++;
52+
for (Stringstr :small) {
53+
// construct all possible words
54+
for (inti =0;i <str.length();i++) {
5455
for (charch ='a';ch <='z';ch++) {
55-
strBuilder.setCharAt(i,ch);
56-
Stringword =strBuilder.toString();
57-
if (word.equals(endWord)) {
58-
// found!
59-
returnwordsInLadder;
60-
}elseif (!visited.contains(word)
61-
&&wordDict.contains(word)) {
62-
// only add new word to next level
63-
next.add(word);
56+
StringBuildersb =newStringBuilder(str);
57+
sb.setCharAt(i,ch);
58+
Stringword =sb.toString();
59+
if (big.contains(word)) {
60+
returnlen;
61+
}
62+
if (wordDict.contains(word) && !visited.contains(word)) {
6463
visited.add(word);
64+
next.add(word);
6565
}
6666
}
6767
}
6868
}
69-
current =next;
69+
if (isBeginSetSmall) {
70+
beginSet =next;
71+
}else {
72+
endSet =next;
73+
}
7074
}
7175
return0;
7276
}
77+
7378
}
Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
/**
2+
* Time : O(); Space: O(N)
3+
* @tag : Breadth-first Search
4+
* @date: Jun 16, 2015
5+
* @by : Steven Cooks
6+
*************************************************************************
7+
* Description:
8+
*
9+
* Given two words (beginWord and endWord), and a dictionary, find the
10+
* length of shortest transformation sequence from beginWord to endWord,
11+
* such that:
12+
* Only one letter can be changed at a time
13+
* Each intermediate word must exist in the dictionary
14+
*
15+
* For example,
16+
* Given: start = "hit" end = "cog"
17+
* dict = ["hot","dot","dog","lot","log"]
18+
* As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
19+
*
20+
* return its length 5.
21+
*
22+
*******************************************************************************
23+
* {@link https://leetcode.com/problems/word-ladder/ }
24+
* -------------------------------------------------------------
25+
* 1. use StringBuilder for repeated string operations
26+
* 2. loop over 'a' - 'z': for (char ch = 'a'; ch <= 'z'; ch++)
27+
*/
28+
package_127_WordLadder;
29+
30+
importjava.util.HashSet;
31+
importjava.util.Set;
32+
33+
/** see test {@link _127_WordLadder.SolutionOneEndTest } */
34+
publicclassSolutionOneEnd {
35+
36+
// construct graph from begin word, and see if end word can be found in some reachable node
37+
publicintladderLength(StringbeginWord,StringendWord,Set<String>wordDict) {
38+
if (beginWord.equals(endWord)) {
39+
return2;
40+
}
41+
Set<String>visited =newHashSet<>();
42+
Set<String>current =newHashSet<>();
43+
current.add(beginWord);
44+
visited.add(beginWord);
45+
46+
intwordsInLadder =1;
47+
intwordLen =beginWord.length();
48+
while (!current.isEmpty()) {
49+
Set<String>next =newHashSet<>();
50+
wordsInLadder++;
51+
// traverse current level
52+
for (Stringstr :current) {
53+
for (inti =0;i <wordLen;i++) {
54+
StringBuilderstrBuilder =newStringBuilder(str);
55+
for (charch ='a';ch <='z';ch++) {
56+
strBuilder.setCharAt(i,ch);
57+
Stringword =strBuilder.toString();
58+
if (word.equals(endWord)) {
59+
// found!
60+
returnwordsInLadder;
61+
}elseif (!visited.contains(word)
62+
&&wordDict.contains(word)) {
63+
// only add new word to next level
64+
next.add(word);
65+
visited.add(word);
66+
}
67+
}
68+
}
69+
}
70+
current =next;
71+
}
72+
return0;
73+
}
74+
75+
}

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp