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

Commitc50d6fa

Browse files
authored
Merge pull requestneetcode-gh#1227 from aakhtar3/2dp
refactor: js | 2dp
2 parentsd5da512 +303c12f commitc50d6fa

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