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

Commit425b077

Browse files
Add C++ implementation
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parentb6d20d9 commit425b077

File tree

2 files changed

+69
-10
lines changed

2 files changed

+69
-10
lines changed

‎0127_word_ladder/word_ladder.c‎

Lines changed: 16 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
#include<stdio.h>
22
#include<stdlib.h>
3+
#include<stdbool.h>
34
#include<string.h>
45

56
#definecontainer_of(ptr,type,member) \
@@ -9,14 +10,10 @@
910
container_of(ptr, type, member)
1011

1112
#definelist_first_entry(ptr,type,field) list_entry((ptr)->next, type, field)
12-
#definelist_last_entry(ptr,type,field) list_entry((ptr)->prev, type, field)
1313

1414
#definelist_for_each(p,head) \
1515
for (p = (head)->next; p != (head); p = p->next)
1616

17-
#definelist_for_each_safe(p,n,head) \
18-
for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
19-
2017
structlist_head {
2118
structlist_head*next,*prev;
2219
};
@@ -78,11 +75,11 @@ static int BKDRHash(char* str, int size)
7875
returnhash %size;
7976
}
8077

81-
staticstructword_node*find(char*word,structlist_head*hheads,intsize)
78+
staticstructword_node*find(char*word,structlist_head*dict,intsize)
8279
{
8380
structlist_head*p;
8481
inthash=BKDRHash(word,size);
85-
list_for_each(p,&hheads[hash]) {
82+
list_for_each(p,&dict[hash]) {
8683
structword_node*node=list_entry(p,structword_node,node);
8784
if (node->step==0&& !strcmp(node->word,word)) {
8885
returnnode;
@@ -98,18 +95,25 @@ static int ladderLength(char* beginWord, char* endWord, char** wordList, int wor
9895
structlist_headqueue;
9996
structword_node*node;
10097

101-
structlist_head*hheads=malloc(wordListSize*sizeof(*hheads));
98+
structlist_head*dict=malloc(wordListSize*sizeof(*dict));
10299
for (i=0;i<wordListSize;i++) {
103-
INIT_LIST_HEAD(hheads+i);
100+
INIT_LIST_HEAD(dict+i);
104101
}
105102

106103
/* Add into hash list */
104+
boolfound= false;
107105
for (i=0;i<wordListSize;i++) {
108106
node=malloc(sizeof(*node));
109107
node->word=wordList[i];
110108
node->step=0;
111109
inthash=BKDRHash(wordList[i],wordListSize);
112-
list_add(&node->node,&hheads[hash]);
110+
list_add(&node->node,&dict[hash]);
111+
if (!strcmp(endWord,wordList[i])) {
112+
found= true;
113+
}
114+
}
115+
if (!found) {
116+
return0;
113117
}
114118

115119
/* FIFO */
@@ -127,8 +131,9 @@ static int ladderLength(char* beginWord, char* endWord, char** wordList, int wor
127131
for (c='a';c <='z';c++) {
128132
if (c==o)continue;
129133
word[i]=c;
130-
node=find(word,hheads,wordListSize);
134+
node=find(word,dict,wordListSize);
131135
if (node!=NULL) {
136+
/* enqueue */
132137
list_add_tail(&node->link,&queue);
133138
node->step=first->step+1;
134139
}
@@ -139,6 +144,7 @@ static int ladderLength(char* beginWord, char* endWord, char** wordList, int wor
139144
if (list_empty(&queue)) {
140145
return0;
141146
}else {
147+
/* dequeue */
142148
first=list_first_entry(&queue,structword_node,link);
143149
list_del(&first->link);
144150
}

‎0127_word_ladder/word_ladder.cc‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#include<bits/stdc++.h>
2+
3+
usingnamespacestd;
4+
5+
classSolution {
6+
public:
7+
intladderLength(string beginWord, string endWord, vector<string>& wordList) {
8+
unordered_set<string>dict(wordList.begin(), wordList.end());
9+
if (!dict.count(endWord)) {
10+
return0;
11+
}
12+
13+
// double BFS
14+
int step =1;
15+
unordered_set<string> s1, s2, tmp, visited;
16+
s1.insert(beginWord);
17+
s2.insert(endWord);
18+
while (!s1.empty() && !s2.empty()) {
19+
if (s1.size() > s2.size()) {
20+
tmp = s1;
21+
s1 = s2;
22+
s2 = tmp;
23+
}
24+
tmp.clear();
25+
26+
for (auto str : s1) {
27+
if (s2.count(str)) {
28+
return step;
29+
}
30+
if (!visited.count(str)) {
31+
visited.insert(str);
32+
}
33+
34+
for (int i =0; i < str.length(); i++) {
35+
char o = str[i];
36+
for (char c ='a'; c <='z'; c++) {
37+
if (c == o)continue;
38+
str[i] = c;
39+
if (dict.count(str) && !visited.count(str)) {
40+
tmp.insert(str);
41+
}
42+
}
43+
str[i] = o;
44+
}
45+
}
46+
47+
// update
48+
s1 = tmp;
49+
step++;
50+
}
51+
return0;
52+
}
53+
};

0 commit comments

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