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

Commite3b464d

Browse files
Refine
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parentfa4cfdd commite3b464d

File tree

2 files changed

+75
-232
lines changed

2 files changed

+75
-232
lines changed

‎0139_word_break/word_break.c‎

Lines changed: 21 additions & 137 deletions
Original file line numberDiff line numberDiff line change
@@ -3,162 +3,46 @@
33
#include<stdbool.h>
44
#include<string.h>
55

6-
#definecontainer_of(ptr,type,member) \
7-
((type *)((char *)(ptr) - (size_t)&(((type *)0)->member)))
86

9-
#definelist_entry(ptr,type,member) \
10-
container_of(ptr, type, member)
11-
12-
#definelist_for_each(p,head) \
13-
for (p = (head)->next; p != (head); p = p->next)
14-
15-
#definelist_for_each_safe(p,n,head) \
16-
for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
17-
18-
structlist_head {
19-
structlist_head*next,*prev;
20-
};
21-
22-
staticinlinevoidINIT_LIST_HEAD(structlist_head*list)
23-
{
24-
list->next=list->prev=list;
25-
}
26-
27-
staticinlineintlist_empty(conststructlist_head*head)
28-
{
29-
return (head->next==head);
30-
}
31-
32-
staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next)
33-
{
34-
next->prev=new;
35-
new->next=next;
36-
new->prev=prev;
37-
prev->next=new;
38-
}
39-
40-
staticinlinevoidlist_add(structlist_head*_new,structlist_head*head)
41-
{
42-
__list_add(_new,head,head->next);
43-
}
44-
45-
staticinlinevoidlist_add_tail(structlist_head*_new,structlist_head*head)
46-
{
47-
__list_add(_new,head->prev,head);
48-
}
49-
50-
staticinlinevoid__list_del(structlist_head*entry)
51-
{
52-
entry->next->prev=entry->prev;
53-
entry->prev->next=entry->next;
54-
}
55-
56-
staticinlinevoidlist_del(structlist_head*entry)
57-
{
58-
__list_del(entry);
59-
entry->next=entry->prev=NULL;
60-
}
61-
62-
structword_node {
63-
char*word;
64-
structlist_headlink;
65-
};
66-
67-
structdfs_cache {
68-
intnum;
69-
intcap;
70-
structlist_head**heads;
71-
};
72-
73-
staticstructdfs_cache*resize(structdfs_cache**caches,intindex)
74-
{
75-
inti;
76-
structdfs_cache*cache=caches[index];
77-
if (cache->num+1>cache->cap) {
78-
cache->cap *=2;
79-
structlist_head**heads=malloc(cache->cap*sizeof(*heads));
80-
for (i=0;i<cache->cap;i++) {
81-
if (i<cache->num) {
82-
heads[i]=cache->heads[i];
83-
}else {
84-
heads[i]=malloc(sizeof(structlist_head));
85-
INIT_LIST_HEAD(heads[i]);
86-
}
87-
}
88-
free(cache->heads);
89-
cache->heads=heads;
90-
}
91-
92-
returncache;
93-
}
94-
95-
staticstructdfs_cache*dfs(char*s,char**words,int*sizes,intnum,
96-
structdfs_cache**caches,intindex)
97-
{
7+
staticintdfs(char*s,char**words,int*lens,intsize,bool*ends,intindex)
8+
{
989
inti,j;
99-
structword_node*wn;
100-
structdfs_cache*result;
101-
10210
if (*s=='\0') {
103-
returnNULL;
104-
}elseif (caches[index]!=NULL) {
105-
returncaches[index];
11+
returntrue;
12+
}elseif (!ends[index]) {
13+
returnfalse;
10614
}else {
107-
result=malloc(sizeof(*result));
108-
result->num=0;
109-
result->cap=1;
110-
result->heads=malloc(sizeof(structlist_head*));
111-
result->heads[0]=malloc(sizeof(structlist_head));
112-
INIT_LIST_HEAD(result->heads[0]);
113-
caches[index]=result;
114-
for (i=0;i<num;i++) {
115-
if (!memcmp(s,words[i],sizes[i])) {
116-
structdfs_cache*next=dfs(s+sizes[i],words,sizes,num,caches,index+sizes[i]);
117-
if (next!=NULL) {
118-
intk=result->num;
119-
for (j=k;j<k+next->num;j++) {
120-
result=resize(caches,index);
121-
wn=malloc(sizeof(*wn));
122-
wn->word=words[i];
123-
list_add(&wn->link,result->heads[j]);
124-
125-
structlist_head*p;
126-
list_for_each(p,next->heads[j-k]) {
127-
structword_node*wnn=list_entry(p,structword_node,link);
128-
wn=malloc(sizeof(*wn));
129-
wn->word=wnn->word;
130-
list_add_tail(&wn->link,result->heads[j]);
131-
}
132-
result->num++;
133-
}
134-
}else {
135-
returnNULL;
15+
for (i=0;i<size;i++) {
16+
ends[index]= false;
17+
if (!strncmp(s,words[i],lens[i])) {
18+
/* post-order traverse */
19+
boolok=dfs(s+lens[i],words,lens,size,ends,index+lens[i]);
20+
if (ok) {
21+
/* string s all matched */
22+
return true;
13623
}
13724
}
13825
}
13926

140-
returnresult;
27+
returnends[index];
14128
}
14229
}
14330

144-
staticboolwordBreak(char*s,char**wordDict,intwordDictSize)
31+
boolwordBreak(char*s,char**wordDict,intwordDictSize)
14532
{
14633
if (wordDictSize==0) {
14734
return false;
14835
}
14936

150-
inti,total=0;
151-
intlen=strlen(s);
152-
int*sizes=malloc(wordDictSize*sizeof(int));
153-
37+
inti,len=strlen(s);
38+
int*lens=malloc(wordDictSize*sizeof(int));
15439
for (i=0;i<wordDictSize;i++) {
155-
sizes[i]=strlen(wordDict[i]);
156-
total+=sizes[i];
40+
lens[i]=strlen(wordDict[i]);
15741
}
15842

159-
structdfs_cache**caches=malloc(len*sizeof(*caches));
160-
memset(caches,0,len*sizeof(*caches));
161-
returndfs(s,wordDict,sizes,wordDictSize,caches,0)==NULL;
43+
bool*ends=malloc(len);
44+
memset(ends, true,len);
45+
returndfs(s,wordDict,lens,wordDictSize,ends,0);
16246
}
16347

16448
intmain(intargc,char**argv)

‎0140_word_break_ii/word_break.c‎

Lines changed: 54 additions & 95 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
#include<stdlib.h>
33
#include<string.h>
44

5+
56
#definecontainer_of(ptr,type,member) \
67
((type *)((char *)(ptr) - (size_t)&(((type *)0)->member)))
78

@@ -11,13 +12,20 @@
1112
#definelist_for_each(p,head) \
1213
for (p = (head)->next; p != (head); p = p->next)
1314

14-
#definelist_for_each_safe(p,n,head) \
15-
for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)
16-
1715
structlist_head {
1816
structlist_head*next,*prev;
1917
};
2018

19+
structword_node {
20+
char*word;
21+
structlist_headlink;
22+
};
23+
24+
structsolution {
25+
intcount;
26+
structlist_headheads[];
27+
};
28+
2129
staticinlinevoidINIT_LIST_HEAD(structlist_head*list)
2230
{
2331
list->next=list->prev=list;
@@ -46,107 +54,58 @@ static inline void list_add_tail(struct list_head *_new, struct list_head *head)
4654
__list_add(_new,head->prev,head);
4755
}
4856

49-
staticinlinevoid__list_del(structlist_head*entry)
57+
staticvoidnew_word_add(structlist_head*head,char*word)
5058
{
51-
entry->next->prev=entry->prev;
52-
entry->prev->next=entry->next;
59+
structword_node*wn=malloc(sizeof(*wn));
60+
wn->word=word;
61+
list_add_tail(&wn->link,head);
5362
}
5463

55-
staticinlinevoidlist_del(structlist_head*entry)
56-
{
57-
__list_del(entry);
58-
entry->next=entry->prev=NULL;
59-
}
60-
61-
structword_node {
62-
char*word;
63-
structlist_headlink;
64-
};
65-
66-
structdfs_cache {
67-
intnum;
68-
intcap;
69-
structlist_head**heads;
70-
};
71-
72-
staticstructdfs_cache*resize(structdfs_cache**caches,intindex)
73-
{
74-
inti;
75-
structdfs_cache*cache=caches[index];
76-
if (cache->num+1>cache->cap) {
77-
cache->cap *=2;
78-
structlist_head**heads=malloc(cache->cap*sizeof(*heads));
79-
for (i=0;i<cache->cap;i++) {
80-
if (i<cache->num) {
81-
heads[i]=cache->heads[i];
82-
}else {
83-
heads[i]=malloc(sizeof(structlist_head));
84-
INIT_LIST_HEAD(heads[i]);
85-
}
86-
}
87-
free(cache->heads);
88-
cache->heads=heads;
89-
}
90-
91-
returncache;
92-
}
93-
94-
staticstructdfs_cache*dfs(char*s,char**words,int*sizes,intnum,
95-
structdfs_cache**caches,intindex)
64+
staticstructsolution*dfs(char*s,char**words,int*lens,intsize,
65+
structsolution**sols,intindex)
9666
{
9767
inti,j;
98-
structword_node*wn;
99-
structdfs_cache*result;
100-
10168
if (*s=='\0') {
10269
returnNULL;
103-
}elseif (caches[index]!=NULL) {
104-
returncaches[index];
70+
}elseif (sols[index]!=NULL) {
71+
returnsols[index];
10572
}else {
106-
result=malloc(sizeof(*result));
107-
result->num=0;
108-
result->cap=1;
109-
result->heads=malloc(sizeof(structlist_head*));
110-
result->heads[0]=malloc(sizeof(structlist_head));
111-
INIT_LIST_HEAD(result->heads[0]);
112-
caches[index]=result;
113-
for (i=0;i<num;i++) {
114-
if (!memcmp(s,words[i],sizes[i])) {
115-
structdfs_cache*next=dfs(s+sizes[i],words,sizes,num,caches,index+sizes[i]);
116-
if (next!=NULL) {
117-
intk=result->num;
118-
for (j=k;j<k+next->num;j++) {
119-
result=resize(caches,index);
120-
wn=malloc(sizeof(*wn));
121-
wn->word=words[i];
122-
list_add(&wn->link,result->heads[j]);
123-
73+
structsolution*sol=malloc(sizeof(*sol)+60*sizeof(structlist_head));
74+
sol->count=0;
75+
sols[index]=sol;
76+
for (i=0;i<size;i++) {
77+
if (!strncmp(s,words[i],lens[i])) {
78+
/* post-order traverse */
79+
structsolution*sub_sol=dfs(s+lens[i],words,lens,size,sols,index+lens[i]);
80+
if (sub_sol!=NULL) {
81+
intk=sol->count;
82+
for (j=k;j<k+sub_sol->count;j++) {
83+
/* Append all sub-solutions */
84+
INIT_LIST_HEAD(&sol->heads[j]);
85+
new_word_add(&sol->heads[j],words[i]);
12486
structlist_head*p;
125-
list_for_each(p,next->heads[j-k]) {
126-
structword_node*wnn=list_entry(p,structword_node,link);
127-
wn=malloc(sizeof(*wn));
128-
wn->word=wnn->word;
129-
list_add_tail(&wn->link,result->heads[j]);
87+
list_for_each(p,&sub_sol->heads[j-k]) {
88+
structword_node*wn=list_entry(p,structword_node,link);
89+
new_word_add(&sol->heads[j],wn->word);
13090
}
131-
result->num++;
91+
sol->count++;
13292
}
13393
}else {
134-
wn=malloc(sizeof(*wn));
135-
wn->word=words[i];
136-
list_add(&wn->link,result->heads[result->num++]);
94+
/* leaf node */
95+
INIT_LIST_HEAD(&sol->heads[0]);
96+
new_word_add(&sol->heads[sol->count++],words[i]);
13797
}
13898
}
13999
}
140-
141-
returnresult;
100+
returnsol;
142101
}
143102
}
144103

145104
/**
146-
** Return an array of size *returnSize.
147-
** Note: The returned array must be malloced, assume caller calls free().
148-
**/
149-
staticchar**wordBreak(char*s,char**wordDict,intwordDictSize,int*returnSize)
105+
* Return an array of size *returnSize.
106+
* Note: The returned array must be malloced, assume caller calls free().
107+
*/
108+
char**wordBreak(char*s,char**wordDict,intwordDictSize,int*returnSize)
150109
{
151110
if (wordDictSize==0) {
152111
*returnSize=0;
@@ -155,24 +114,24 @@ static char **wordBreak(char* s, char** wordDict, int wordDictSize, int *returnS
155114

156115
inti,total=0;
157116
intlen=strlen(s);
158-
int*sizes=malloc(wordDictSize*sizeof(int));
117+
int*lens=malloc(wordDictSize*sizeof(int));
159118

160119
/* Add into hash list */
161120
for (i=0;i<wordDictSize;i++) {
162-
sizes[i]=strlen(wordDict[i]);
163-
total+=sizes[i];
121+
lens[i]=strlen(wordDict[i]);
122+
total+=lens[i];
164123
}
165124

166-
structdfs_cache**caches=malloc(len*sizeof(*caches));
167-
memset(caches,0,len*sizeof(*caches));
168-
structdfs_cache*cache=dfs(s,wordDict,sizes,wordDictSize,caches,0);
125+
structsolution**sols=malloc(len*sizeof(void*));
126+
memset(sols,0,len*sizeof(void*));
127+
structsolution*sol=dfs(s,wordDict,lens,wordDictSize,sols,0);
169128

170-
char**results=malloc(cache->num*sizeof(char*));
171-
for (i=0;i<cache->num;i++) {
129+
char**results=malloc(sol->count*sizeof(char*));
130+
for (i=0;i<sol->count;i++) {
172131
results[i]=malloc(total+100);
173132
char*p=results[i];
174133
structlist_head*n;
175-
list_for_each(n,cache->heads[i]) {
134+
list_for_each(n,&sol->heads[i]) {
176135
structword_node*wn=list_entry(n,structword_node,link);
177136
char*q=wn->word;
178137
while ((*p++=*q++)!='\0') {}
@@ -181,7 +140,7 @@ static char **wordBreak(char* s, char** wordDict, int wordDictSize, int *returnS
181140
*(p-1)='\0';
182141
}
183142

184-
*returnSize=cache->num;
143+
*returnSize=sol->count;
185144
returnresults;
186145
}
187146

0 commit comments

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