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

Commit9cbc6c0

Browse files
committed
String problems + dynamic programming, add 127, 131, 132, 139
1 parentd013ca2 commit9cbc6c0

File tree

6 files changed

+227
-1
lines changed

6 files changed

+227
-1
lines changed
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/**
2+
*@param {string} s
3+
*@return {number}
4+
*/
5+
6+
varminCut=function(s){
7+
if(!s)return0;
8+
varlength=s.length;
9+
varisPal=[];
10+
for(vari=length-1;i>=0;i--){
11+
isPal[i]=[];
12+
for(varj=i;j<length;j++){
13+
if((j-i<=2||isPal[i+1][j-1])&&s[i]==s[j])
14+
isPal[i][j]=true;
15+
}
16+
}
17+
18+
varcut=[-1];
19+
for(i=1;i<=length;i++){
20+
cut[i]=i;
21+
for(j=i-1;j>=0;j--){
22+
if(isPal[j][i-1]){
23+
cut[i]=Math.min(cut[i],cut[j]+1);
24+
}
25+
}
26+
}
27+
returncut[length];
28+
};
29+
30+
// not working Time exceeds limits.
31+
varminCut=function(s){
32+
varresult=[];
33+
varmin={min:Math.pow(2,31)-1};
34+
if(!s)returnmin;
35+
varx=helper(s,0,result,min);
36+
returnx.min;
37+
};
38+
39+
varhelper=function(s,start,result,min){
40+
if(start>=s.length){
41+
if(result.length-1<min.min){
42+
min.min=result.length-1;
43+
}
44+
}
45+
46+
for(vari=start;i<s.length;i++){
47+
varnewStr=s.substring(start,i+1);
48+
if(isPalindrome(newStr)){
49+
result.push(newStr);
50+
helper(s,i+1,result,min);
51+
result.pop();
52+
}
53+
}
54+
55+
returnmin;
56+
};
57+
58+
varisPalindrome=function(s){
59+
if(!s||s.length===1)returntrue;
60+
varlength=s.length;
61+
for(vari=0;i<length;i++){
62+
if(s[i]!==s[length-i-1])returnfalse;
63+
}
64+
65+
returntrue;
66+
};

‎Medium/127-wordLadder.js‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/**
2+
* Solution: BFS
3+
* use a queue to save candidates from wordList on each level.
4+
* find next next candiate from the queue.
5+
*
6+
*@param {string} beginWord
7+
*@param {string} endWord
8+
*@param {Set} wordList
9+
* Note: wordList is a Set object, see:
10+
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
11+
*@return {number}
12+
*/
13+
varladderLength=function(beginWord,endWord,wordList){
14+
if(!beginWord)return0;
15+
varqueue=[beginWord];
16+
varstep=1;
17+
wordList.add(endWord);
18+
while(queue.length>0){
19+
varqueueLength=queue.length;
20+
for(vari=0;i<queueLength;i++){
21+
varword=queue.shift();
22+
if(word===endWord)returnstep;
23+
for(vark=0;k<word.length;k++){
24+
vartmp=word[k];
25+
for(varj=97;j<=122;j++){
26+
if(word.charCodeAt(k)!==j){
27+
charAtK=String.fromCharCode(j);
28+
word=word.substring(0,k)+charAtK+word.substring(k+1);
29+
if(wordList.has(word)){
30+
// save the candidate to the queue of this level
31+
queue.push(word);
32+
// meanwhile, delete this candidate from wordList
33+
wordList.delete(word);
34+
}
35+
}
36+
}
37+
// reset word, for next character change
38+
word=word.substring(0,k)+tmp+word.substring(k+1);
39+
}
40+
}
41+
step++;
42+
}
43+
44+
return0;
45+
};
46+
47+
// for testing
48+
// var a = 'hit';
49+
// var b = 'cog';
50+
// var set = new Set(["hot","dot","dog","lot","log"]);
51+
// var a = 'a';
52+
// var b = 'c';
53+
// var set = new Set(['a', 'b', 'c']);
54+
// console.log(ladderLength(a, b, set));
Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
/**
2+
* Solution: backtracking, DFS
3+
*
4+
*@param {string} s
5+
*@return {string[][]}
6+
*/
7+
varpartition=function(s){
8+
varresult=[];
9+
varresults=[];
10+
if(!s)returnresults;
11+
helper(s,0,result,results);
12+
returnresults;
13+
};
14+
15+
varhelper=function(s,start,result,results){
16+
if(start>=s.length){
17+
results.push(result.slice());
18+
result=[];
19+
}
20+
21+
for(vari=start;i<s.length;i++){
22+
varnewStr=s.substring(start,i+1);
23+
if(isPalindrome(newStr)){
24+
result.push(newStr);
25+
helper(s,i+1,result,results);
26+
result.pop();
27+
}
28+
}
29+
};
30+
31+
varisPalindrome=function(s){
32+
if(!s||s.length===1)returntrue;
33+
varlength=s.length;
34+
for(vari=0;i<length;i++){
35+
if(s[i]!==s[length-i-1])returnfalse;
36+
}
37+
38+
returntrue;
39+
};
40+
41+
// testing cases
42+
// var s = 'aab';
43+
// console.log(partition(s));
44+
45+
// second method, use a dp matrix. (isPal)
46+
// Same O(n^2), but faster
47+
varpartition=function(s){
48+
varresult=[];
49+
varresults=[];
50+
if(!s)returnresults;
51+
varlength=s.length;
52+
varisPal=[];
53+
for(vari=length-1;i>=0;i--){
54+
isPal[i]=[];
55+
for(varj=i;j<length;j++){
56+
if((j-i<=2||isPal[i+1][j-1])&&s[i]==s[j])
57+
isPal[i][j]=true;
58+
}
59+
}
60+
61+
helper(s,0,result,results,isPal);
62+
returnresults;
63+
};
64+
65+
varhelper=function(s,start,result,results,isPal){
66+
if(start>=s.length){
67+
results.push(result.slice());
68+
return;
69+
}
70+
71+
for(vari=start;i<s.length;i++){
72+
if(isPal[start][i]){
73+
result.push(s.substring(start,i+1));
74+
helper(s,i+1,result,results,isPal);
75+
result.pop();
76+
}
77+
}
78+
};

‎Medium/139-wordBreak.js‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
*@param {string} s
3+
*@param {set<string>} wordDict
4+
* Note: wordDict is a Set object, see:
5+
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
6+
*@return {boolean}
7+
*/
8+
9+
// recursion, not accepted, time exceeds limits.
10+
varwordBreak=function(s,wordDict){
11+
returnhelper(s,wordDict,0);
12+
};
13+
14+
varhelper=function(s,wordDict,start){
15+
if(start===s.length)returntrue;
16+
// also let ... of is an ES6 feature
17+
for(varwordofwordDict){
18+
varwLength=word.length;
19+
if(s.substring(start,start+wLength)===word){
20+
if(helper(s,wordDict,start+wLength))returntrue;
21+
}
22+
}
23+
returnfalse;
24+
};

‎Medium/5-longestPalindromicSubstring.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/**
2-
* Key: see inline comments. O(N^2)
2+
* Key: see inline comments. O(N^2). Space O(1).
33
*
44
*@param {string} s
55
*@return {string}

‎README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -127,8 +127,11 @@
127127
*[121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) -[Solution](./Medium/121-bestTimeToBuySellStock.js)
128128
*[122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/) -[Solution](./Medium/122-bestTimeToBuySellStockII.js)
129129
*[129. Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers/) -[Solution](./Medium/129-sumRootToLeafNumbers.js)
130+
*[127. Word Ladder](https://leetcode.com/problems/word-ladder/) -[Solution](./Medium/127-wordLadder.js)
131+
*[131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/) -[Solution](./Medium/131-palindromePartitioning.js)
130132
*[134. Gas Station](https://leetcode.com/problems/gas-station/) -[Solution](./Medium/134-gasStation.js)
131133
*[136. Single Number](https://leetcode.com/problems/single-number/) -[Solution](./Medium/136-singleNumber.js)
134+
*[139. Word Break](https://leetcode.com/problems/word-break/) -[Solution](./Medium/139-wordBreak.js)
132135
*[141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) -[Solution](./Medium/141-linkedListCycle.js)
133136
*[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) -[Solution](./Medium/144-binaryTreePreorder.js)
134137
*[153.Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) -[Solution](./Medium/153-findMinimumInRotatedSortedArray.js)
@@ -160,4 +163,5 @@
160163
*[56. Merge Intervals](https://leetcode.com/problems/merge-intervals/) -[Solution](./Hard/56-MergeIntervals.js)
161164
*[57. Insert Interval](https://leetcode.com/problems/insert-interval/) -[Solution](./Hard/57-insertInterval.js)
162165
*[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)
166+
*[132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/) -[Solution](./Hard/132-palindromePartitioningII.js)
163167
*[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