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

Commit303c12f

Browse files
committed
refactor: js | 2dp
1 parent18ee23d commit303c12f

11 files changed

+1307
-342
lines changed
Lines changed: 86 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -1,38 +1,98 @@
11
/**
2+
* Brute Force - DFS
3+
* Time O((N + M) * 2^(N + (M / 2))) | Space O(N^2 + M^2)
4+
* https://leetcode.com/problems/regular-expression-matching/
25
*@param {string} s
36
*@param {string} p
47
*@return {boolean}
58
*/
6-
varisMatch=function(s,p){
7-
varlenS=s.length;
8-
varlenP=p.length;
9-
varmap={};
9+
varisMatch=(text,pattern)=>{
10+
constisBaseCase=(pattern.length===0);
11+
if(isBaseCase)return(text.length===0);
1012

11-
returncheck(0,0);
13+
constisTextAndPatternEqual=(pattern[0]===text[0]),
14+
isPatternPeriod=(pattern[0]==='.'),
15+
isFirstMatch=(text&&(isTextAndPatternEqual||isPatternPeriod)),
16+
isNextPatternWildCard=(pattern.length>=2&&pattern[1]==='*');
1217

13-
functioncheck(idxS,idxP){
14-
if(map[idxS+':'+idxP]!==undefined){
15-
returnmap[idxS+':'+idxP];
16-
}
18+
returnisNextPatternWildCard/* Time O((N + M) * 2^(N + (M / 2))) | Space O(N^2 + M^2) */
19+
?(isMatch(text,pattern.slice(2))||(isFirstMatch&&isMatch(text.slice(1),pattern)))
20+
:(isFirstMatch&&isMatch(text.slice(1),pattern.slice(1)));
21+
};
1722

18-
if(idxS>lenS){
19-
returnfalse;
20-
}
23+
/**
24+
* DP - Top Down
25+
* Matrix - Memoization
26+
* Time O(N * M) | Space O(N * M)
27+
* https://leetcode.com/problems/regular-expression-matching/
28+
*@param {string} s
29+
*@param {string} p
30+
*@return {boolean}
31+
*/
32+
varisMatch=(text,pattern,row=0,col=0,memo=initMemo(text,pattern))=>{
33+
consthasSeen=(memo[row][col]);
34+
if(hasSeen)returnmemo[row][col];
2135

22-
if(idxS===lenS&&idxP===lenP){
23-
returntrue;
24-
}
36+
constisEqual=(col===pattern.length);
37+
constans=isEqual
38+
?row===text.length
39+
:check(text,pattern,row,col,memo);/* Time O(N * M) | Space O(N * M) */
2540

26-
if(p[idxP]==='.'||p[idxP]===s[idxS]){
27-
map[idxS+':'+idxP]=
28-
p[idxP+1]==='*'
29-
?check(idxS+1,idxP)||check(idxS,idxP+2)
30-
:check(idxS+1,idxP+1);
31-
}else{
32-
map[idxS+':'+idxP]=
33-
p[idxP+1]==='*' ?check(idxS,idxP+2) :false;
34-
}
41+
memo[row][col]=ans;
42+
returnans;
43+
}
44+
45+
varinitMemo=(text,pattern)=>newArray((text.length+1)).fill()/* Time O(N) | Space O(N) */
46+
.map(()=>newArray((pattern.length+1)).fill(false))/* Time O(M) | Space O(M) */
47+
48+
varcheck=(text,pattern,row,col,memo)=>{
49+
constisTextDefined=(row<text.length),
50+
isTextAndPatternEqual=(pattern[col]===text[row]),
51+
isPatternPeriod=(pattern[col]==='.'),
52+
isFirstMatch=(isTextDefined&&(isTextAndPatternEqual||isPatternPeriod)),
53+
isNextPatternWildCard=(((col+1)<pattern.length)&&pattern[col+1]==='*');
54+
55+
returnisNextPatternWildCard/* Time O(N * M) | Space O(N * M) */
56+
?(isMatch(text,pattern,row,(col+2),memo)||isFirstMatch&&isMatch(text,pattern,(row+1),col,memo))
57+
:(isFirstMatch&&isMatch(text,pattern,(row+1),(col+1),memo));
58+
}
59+
60+
/**
61+
* Time O(N * M) | Space O(N * M)
62+
*@param {string} s
63+
*@param {string} p
64+
*@return {boolean}
65+
*/
66+
varisMatch=(text,pattern)=>{
67+
consttabu=initTabu(text,pattern);/* Time O(N * M) | Space O(N * M) */
68+
69+
search(text,pattern,tabu);/* Time O(N * M) | Space O(N * M) */
70+
71+
returntabu[0][0];
3572

36-
returnmap[idxS+':'+idxP];
73+
}
74+
75+
varinitTabu=(text,pattern)=>{
76+
consttabu=newArray((text.length+1)).fill()/* Time O(N) | Space O(N) */
77+
.map(()=>newArray((pattern.length+1)).fill(false));/* Time O(M) | Space O(M) */
78+
79+
tabu[text.length][pattern.length]=true;/* | Space O(N * M) */
80+
81+
returntabu
82+
}
83+
84+
varsearch=(text,pattern,tabu)=>{
85+
for(letrow=text.length;0<=row;row--){/* Time O(N) */
86+
for(letcol=(pattern.length-1);(0<=col);col--){/* Time O(M) */
87+
constisTextDefined=row<text.length,
88+
isTextAndPatternEqual=pattern[col]===text[row],
89+
isPatternPeriod=pattern[col]==='.',
90+
isFirstMatch=isTextDefined&&(isTextAndPatternEqual||isPatternPeriod),
91+
isNextPatternWildCard=col+1<pattern.length&&pattern[col+1]==='*';
92+
93+
tabu[row][col]=isNextPatternWildCard/* Space O(N * M) */
94+
?tabu[row][col+2]||(isFirstMatch&&tabu[row+1][col])
95+
:isFirstMatch&&tabu[row+1][col+1];
96+
}
3797
}
38-
};
98+
}
Lines changed: 141 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,144 @@
1-
varlongestCommonSubsequence=function(text1,text2){
2-
letm=text1.length,
3-
n=text2.length,
4-
DP=newArray(m+1).fill(0).map((_)=>newArray(n+1).fill(0));
5-
6-
for(letx=m-1;x>=0;x--)
7-
for(lety=n-1;y>=0;y--){
8-
if(text1[x]===text2[y]){
9-
DP[x][y]=1+DP[x+1][y+1];
10-
}else{
11-
DP[x][y]=Math.max(DP[x+1][y],DP[x][y+1]);
12-
}
1+
/**
2+
* DP - Top Down
3+
* Matrix - Memoization
4+
* Time O(N * (M^2)) | Space O(N * M)
5+
* https://leetcode.com/problems/longest-common-subsequence/
6+
*@param {string} text1
7+
*@param {string} text2
8+
*@return {number}
9+
*/
10+
varlongestCommonSubsequence=(text1,text2,p1=0,p2=0,memo=initMemo(text1,text2))=>{
11+
constisBaseCase=((p1===text1.length)||(p2===text2.length));
12+
if(isBaseCase)return0;
13+
14+
consthasSeen=(memo[p1][p2]!==null);
15+
if(hasSeen)returnmemo[p1][p2];
16+
17+
returndfs(text1,text2,p1,p2,memo);/* Time O((N * M) * M)) | Space O((N * M) + HEIGHT) */
18+
}
19+
20+
varinitMemo=(text1,text2)=>newArray((text1.length+1)).fill()/* Time O(N) | Space O(N) */
21+
.map(()=>newArray((text2.length+1)).fill(null));/* Time O(M) | Space O(M) */
22+
23+
vardfs=(text1,text2,p1,p2,memo)=>{
24+
constleft=longestCommonSubsequence(text1,text2,(p1+1),p2,memo);/* Time O(N * M) | Space O(HEIGHT) */
25+
26+
constindex=text2.indexOf(text1[p1],p2);/* Time O(M) */
27+
constisPrefix=(index!==-1);
28+
29+
constright=isPrefix
30+
?(longestCommonSubsequence(text1,text2,(p1+1),(index+1),memo)+1)/* Time O(N * M) | Space O(HEIGHT) */
31+
:0;
32+
33+
memo[p1][p2]=Math.max(left,right);/* | Space O(N * M) */
34+
returnmemo[p1][p2];
35+
}
36+
37+
/**
38+
* DP - Top Down
39+
* Matrix - Memoization
40+
* Time O(N * M) | Space O(N * M)
41+
* https://leetcode.com/problems/longest-common-subsequence/
42+
*@param {string} text1
43+
*@param {string} text2
44+
*@return {number}
45+
*/
46+
varlongestCommonSubsequence=(text1,text2,p1=0,p2=0,memo=initMemo(text1,text2))=>{
47+
constisBaseCase=((p1===text1.length)||(p2===text2.length));
48+
if(isBaseCase)return0;
49+
50+
consthasSeen=(memo[p1][p2]!==null);
51+
if(hasSeen)returnmemo[p1][p2];
52+
53+
returndfs(text1,text2,p1,p2,memo);/* Time O(N * M) | Space O((N * M) + HEIGHT) */
54+
}
55+
56+
varinitMemo=(text1,text2)=>newArray((text1.length+1)).fill()/* Time O(N) | Space O(N) */
57+
.map(()=>newArray((text2.length+1)).fill(null));/* Time O(M) | Space O(M) */
58+
59+
vardfs=(text1,text2,p1,p2,memo)=>{
60+
constleft=(longestCommonSubsequence(text1,text2,(p1+1),(p2+1),memo)+1);/* Time O(N * M) | Space O(HEIGHT) */
61+
constright=/* Time O(N * M) | Space O(HEIGHT) */
62+
Math.max(longestCommonSubsequence(text1,text2,p1,(p2+1),memo),longestCommonSubsequence(text1,text2,(p1+1),p2,memo));
63+
64+
constisEqual=(text1[p1]==text2[p2]);
65+
constcount=isEqual
66+
?left
67+
:right
68+
69+
memo[p1][p2]=count;/* | Space O(N * M) */
70+
returnmemo[p1][p2];
71+
}
72+
73+
/**
74+
* DP - Bottom Up
75+
* Matrix - Tabulation
76+
* Time O(N * M) | Space O(N * M)
77+
* https://leetcode.com/problems/longest-common-subsequence/
78+
*@param {string} text1
79+
*@param {string} text2
80+
*@return {number}
81+
*/
82+
varlongestCommonSubsequence=(text1,text2)=>{
83+
consttabu=initTabu(text1,text2);/* Time O(N * M) | Space O(N * M) */
84+
85+
search(text1,text2,tabu);/* Time O(N * M) | Space O(N * M) */
86+
87+
returntabu[0][0];
88+
};
89+
90+
varinitTabu=(text1,text2)=>
91+
newArray((text1.length+1)).fill()/* Time O(N) | Space O(N) */
92+
.map(()=>newArray((text2.length+1)).fill(0));/* Time O(M) | Space O(M) */
93+
94+
varsearch=(text1,text2,tabu)=>{
95+
const[n,m]=[text1.length,text2.length];
96+
97+
for(letx=(n-1);(0<=x);x--){/* Time O(N) */
98+
for(lety=(m-1);(0<=y);y--){/* Time O(M) */
99+
tabu[x][y]=(text1[x]===text2[y])/* Space O(N * M) */
100+
?(tabu[x+1][y+1]+1)
101+
:Math.max(tabu[x+1][y],tabu[x][y+1]);
13102
}
103+
}
104+
}
105+
106+
/**
107+
* DP - Bottom Up
108+
* Matrix - Tabulation
109+
* Time O(N * M) | Space O(M)
110+
* https://leetcode.com/problems/longest-common-subsequence/
111+
*@param {string} text1
112+
*@param {string} text2
113+
*@return {number}
114+
*/
115+
varlongestCommonSubsequence=(text1,text2)=>{
116+
constcanSwap=(text2.length<text1.length);
117+
if(canSwap)[text1,text2]=[text2,text1];
118+
119+
lettabu=initTabu(text1);/* Time O(M) | Space O(M) */
120+
121+
tabu=search(text1,text2,tabu);/* Time O(N * M) | Space O(M) */
14122

15-
returnDP[0][0];
123+
returntabu[0];
16124
};
125+
126+
varinitTabu=(text1)=>newArray((text1.length+1)).fill(0)
127+
128+
varsearch=(text1,text2,tabu)=>{
129+
for(letcol=(text2.length-1);(0<=col);col--){/* Time O(N) */
130+
consttemp=initTabu(text1);/* Space O(M) */
131+
132+
for(letrow=(text1.length-1);(0<=row);row--){/* Time O(M) */
133+
constisEqual=(text1[row]==text2[col]);
134+
135+
temp[row]=isEqual/* Space O(M) */
136+
?(tabu[(row+1)]+1)
137+
:Math.max(tabu[row],temp[(row+1)]);
138+
}
139+
140+
tabu=temp;/* Space O(M) */
141+
}
142+
143+
returntabu;
144+
}

0 commit comments

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