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

Commitb33e440

Browse files
committed
127-word-ladder.md Simplified the Python solution.
1 parent361b8aa commitb33e440

File tree

2 files changed

+69
-69
lines changed

2 files changed

+69
-69
lines changed

‎en/1-1000/127-word-ladder.md‎

Lines changed: 34 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -55,57 +55,57 @@ getting `shortest` or `least` of something of a graph, `breadth-first search` wo
5555
1. So through`Breadth-First Search`, when a word matches`endWord`, the game is over, and we can return the number of**circle** as a result.
5656

5757
##Complexity
58-
* Time:`O(n *n)`.
59-
* Space:`O(n)`.
58+
* Time:`O((26 *end_word.length) * N)`.
59+
* Space:`O(N)`.
6060

6161
##Python
6262
```python
63-
classSolution:
64-
def__init__(self):
65-
self.word_set=None
66-
self.end_word=None
67-
self.queue= deque()
63+
from collectionsimport deque
6864

65+
classSolution:
6966
defladderLength(self,begin_word:str,end_word:str,word_list: List[str]) ->int:
70-
self.end_word= end_word
71-
self.word_set=set(word_list)
67+
words=set(word_list)
7268

73-
if end_wordnotinself.word_set:
69+
if end_wordnotinwords:
7470
return0
75-
76-
self.queue.append((begin_word,1))
7771

78-
returnself.breadth_first_search()
72+
if begin_word== end_word:
73+
return1
74+
75+
queue= deque([begin_word])
7976

80-
defbreadth_first_search(self):
81-
whileself.queue:
82-
word0, circle=self.queue.popleft()
83-
removed_words=set()
77+
if begin_wordin words:
78+
words.remove(begin_word)
8479

85-
for wordinself.word_set:
86-
if one_char_different(word, word0):
87-
if word==self.end_word:
88-
return circle+1
80+
result=0
8981

90-
self.queue.append((word, circle+1))
82+
while queue:
83+
size=len(queue)
84+
result+=1
9185

92-
removed_words.add(word)
93-
94-
self.word_set-= removed_words
86+
for iinrange(size):
87+
current_word= queue.popleft()
88+
89+
for wordin one_letter_changed_words(current_word):
90+
if word== end_word:
91+
return result+1
92+
93+
if wordin words:
94+
queue.append(word)
95+
words.remove(word)
9596

9697
return0
9798

9899

99-
defone_char_different(word1,word2):
100-
different_char_count=0
100+
defone_letter_changed_words(word):
101+
words= []
102+
103+
for iinrange(len(word)):
104+
for letterin'abcdefghijklmnopqrstuvwxyz':
105+
if letter!= word[i]:
106+
words.append(word[:i]+ letter+ word[i+1:])
101107

102-
for iinrange(len(word1)):
103-
if word1[i]!= word2[i]:
104-
different_char_count+=1
105-
if different_char_count>1:
106-
returnFalse
107-
108-
returnTrue
108+
return words
109109
```
110110

111111
##Java

‎zh/1-1000/127-word-ladder.md‎

Lines changed: 35 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ The **word transformation sequence** problem can be abstracted into a **graph th
4646
![](../../images/binary_tree_BFS_1.gif)
4747

4848
* As shown in the figure above,**breadth-first search** can be thought of as visiting vertices in rounds and rounds. Actually, whenever you see a question is about
49-
getting`shortest` or`least` of something of a graph,`breadth-first search` would probably help.
49+
getting`shortest` or`least` of something of a graph,`breadth-first search` would probably help.
5050

5151
*`breadth-first search` emphasizes first-in-first-out, so a**queue** is needed.
5252

@@ -55,57 +55,57 @@ getting `shortest` or `least` of something of a graph, `breadth-first search` wo
5555
1. So through`Breadth-First Search`, when a word matches`endWord`, the game is over, and we can return the number of**circle** as a result.
5656

5757
##Complexity
58-
* Time:`O(n *n)`.
59-
* Space:`O(n)`.
58+
* Time:`O((26 *end_word.length) * N)`.
59+
* Space:`O(N)`.
6060

6161
##Python
6262
```python
63-
classSolution:
64-
def__init__(self):
65-
self.word_set=None
66-
self.end_word=None
67-
self.queue= deque()
63+
from collectionsimport deque
6864

65+
classSolution:
6966
defladderLength(self,begin_word:str,end_word:str,word_list: List[str]) ->int:
70-
self.end_word= end_word
71-
self.word_set=set(word_list)
67+
words=set(word_list)
7268

73-
if end_wordnotinself.word_set:
69+
if end_wordnotinwords:
7470
return0
75-
76-
self.queue.append((begin_word,1))
7771

78-
returnself.breadth_first_search()
72+
if begin_word== end_word:
73+
return1
74+
75+
queue= deque([begin_word])
7976

80-
defbreadth_first_search(self):
81-
whileself.queue:
82-
word0, circle=self.queue.popleft()
83-
removed_words=set()
77+
if begin_wordin words:
78+
words.remove(begin_word)
8479

85-
for wordinself.word_set:
86-
if one_char_different(word, word0):
87-
if word==self.end_word:
88-
return circle+1
80+
result=0
8981

90-
self.queue.append((word, circle+1))
82+
while queue:
83+
size=len(queue)
84+
result+=1
9185

92-
removed_words.add(word)
93-
94-
self.word_set-= removed_words
86+
for iinrange(size):
87+
current_word= queue.popleft()
88+
89+
for wordin one_letter_changed_words(current_word):
90+
if word== end_word:
91+
return result+1
92+
93+
if wordin words:
94+
queue.append(word)
95+
words.remove(word)
9596

9697
return0
9798

9899

99-
defone_char_different(word1,word2):
100-
different_char_count=0
100+
defone_letter_changed_words(word):
101+
words= []
102+
103+
for iinrange(len(word)):
104+
for letterin'abcdefghijklmnopqrstuvwxyz':
105+
if letter!= word[i]:
106+
words.append(word[:i]+ letter+ word[i+1:])
101107

102-
for iinrange(len(word1)):
103-
if word1[i]!= word2[i]:
104-
different_char_count+=1
105-
if different_char_count>1:
106-
returnFalse
107-
108-
returnTrue
108+
return words
109109
```
110110

111111
##Java

0 commit comments

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