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

Commit6259876

Browse files
committed
dynamic palindrome questins 5, 132. Distinct substring 115
1 parentde7ba71 commit6259876

File tree

4 files changed

+112
-0
lines changed

4 files changed

+112
-0
lines changed

‎Hard/115-distinctSubsequences.js‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/**
2+
* Solution: Dynamic programming
3+
* match[i][j], the number of matched substrings when s with the length i and t with the length j.
4+
* if s[i-1] !== s[j-1], then the matched number equals to the matched number of s with length i - 1.
5+
* that is, match[i][j] = match[i-1][j].
6+
* if s[i-1] == s[j-1], the matched number is the mathched number when s with length i - 1 and t with length j,
7+
* plus the matched number when s with i - 1 length and t with j - 1 length.
8+
*
9+
*@param {string} s
10+
*@param {string} t
11+
*@return {number}
12+
*/
13+
varnumDistinct=function(s,t){
14+
if(!s)return0;
15+
16+
varmatch=[];
17+
for(vari=0;i<=s.length;i++){
18+
match[i]=[1];
19+
}
20+
21+
for(varj=1;j<=t.length;j++){
22+
match[0][j]=0;
23+
}
24+
25+
for(i=1;i<=s.length;i++){
26+
for(j=1;j<=t.length;j++){
27+
if(s[i-1]===t[j-1])match[i][j]=match[i-1][j-1]+match[i-1][j];
28+
elsematch[i][j]=match[i-1][j];
29+
}
30+
}
31+
32+
returnmatch[s.length][t.length];
33+
34+
};
35+
36+
// just use one dimension array to store matched numbers
37+
varnumDistinct=function(s,t){
38+
if(!s)return0;
39+
if(t.length>s.length)return0;
40+
41+
vartLength=t.length;
42+
varsLength=s.length;
43+
44+
vardp=[1];
45+
for(vari=1;i<=tLength;i++){
46+
dp.push(0);
47+
}
48+
49+
for(i=1;i<=sLength;i++){
50+
for(j=tLength;j>=1;j--){
51+
if(s[i-1]===t[j-1])dp[j]+=dp[j-1];
52+
}
53+
}
54+
55+
returndp[tLength];
56+
57+
};
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
/**
2+
*@param {string} s
3+
*@return {number}
4+
*/
5+
varminCut=function(s){
6+
if(!s)return0;
7+
varlength=s.length;
8+
varisPal=[];
9+
for(vari=length-1;i>=0;i--){
10+
isPal[i]=[];
11+
for(varj=i;j<length;j++){
12+
if((j-i<=2||isPal[i+1][j-1])&&s[i]==s[j])
13+
isPal[i][j]=true;
14+
}
15+
}
16+
17+
varcut=[-1];
18+
for(i=1;i<=length;i++){
19+
cut[i]=i;
20+
for(j=i-1;j>=0;j--){
21+
if(isPal[j][i-1]){
22+
cut[i]=Math.min(cut[i],cut[j]+1);
23+
}
24+
}
25+
}
26+
returncut[length];
27+
};

‎Medium/5-longestPalindromicSubstring.js‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,3 +34,29 @@ var getPalindromeSubstring = function(s, i, j) {
3434

3535
returns.substring(i+1,j);
3636
};
37+
38+
39+
// dp method, should work. memory exceed limit
40+
// bottom-up.
41+
varlongestPalindrome=function(s){
42+
if(!s)returns;
43+
varlongest=s.substring(0,1);
44+
varlength=s.length;
45+
vardp=[];
46+
varmaxLength=1;
47+
for(vari=length-1;i>=0;i--){
48+
dp[i]=[];
49+
for(varj=i;j<length;j++){
50+
// j - i <= 2 is important, in case i + 1 is out of array boundary.
51+
if(s[i]===s[j]&&(j-i<=2||dp[i+1][j-1])){
52+
dp[i][j]=true;
53+
if(j-i+1>maxLength){
54+
maxLength=j-i+1;
55+
longest=s.substring(i,j+1);
56+
}
57+
}
58+
}
59+
}
60+
61+
returnlongest;
62+
};

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -162,5 +162,7 @@
162162
*[33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/) -[Solution](./Hard/33-searchRotatedSortedArray.js)
163163
*[56. Merge Intervals](https://leetcode.com/problems/merge-intervals/) -[Solution](./Hard/56-MergeIntervals.js)
164164
*[57. Insert Interval](https://leetcode.com/problems/insert-interval/) -[Solution](./Hard/57-insertInterval.js)
165+
*[115. Distinct Subsequences](https://leetcode.com/problems/distinct-subsequences/) -[Solution](./Hard/115-distinctSubsequences.js)
165166
*[123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/) -[Solution](./Hard/123-bestTimeBuySellStockIII.js)
167+
*[132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/) -[Solution](./Hard/132-palindromePartitioningII.js)
166168
*[154.Find Minimum in Rotated Sorted Array II](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/) -[Solution](./Hard/154-findMinimumInRotatedSortedArray-II.js)

0 commit comments

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