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

Commitcb53c8c

Browse files
committed
fix:Updated palindromePartition algorithm
1 parent4bdaa5c commitcb53c8c

File tree

4 files changed

+86
-75
lines changed

4 files changed

+86
-75
lines changed

‎Backtracking/PalindromePartitioning.js

Lines changed: 0 additions & 46 deletions
This file was deleted.

‎Backtracking/tests/PalindromePartitioning.test.js

Lines changed: 0 additions & 29 deletions
This file was deleted.

‎Recursive/PalindromePartitioning.js

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
/*
2+
* Problem Statement: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
3+
* what is palindrome partitioning?
4+
* - Palindrome partitioning means, partitioning a string into substrings such that every substring is a palindrome.
5+
* Reference to know more about palindrome partitioning:
6+
* - https://www.cs.columbia.edu/~sedwards/classes/2021/4995-fall/proposals/Palindrome.pdf
7+
*/
8+
9+
// class PalindromePartitioning {
10+
// partition(s) {
11+
// const result = []
12+
// this.backtrack(s, [], result)
13+
// return result
14+
// }
15+
16+
// backtrack(s, path, result) {
17+
// if (s.length === 0) {
18+
// result.push([...path])
19+
// return
20+
// }
21+
22+
// for (let i = 0; i < s.length; i++) {
23+
// const prefix = s.substring(0, i + 1)
24+
// if (this.isPalindrome(prefix)) {
25+
// path.push(prefix)
26+
// this.backtrack(s.substring(i + 1), path, result)
27+
// path.pop()
28+
// }
29+
// }
30+
// }
31+
32+
// isPalindrome(s) {
33+
// let start = 0
34+
// let end = s.length - 1
35+
// while (start < end) {
36+
// if (s.charAt(start) !== s.charAt(end)) {
37+
// return false
38+
// }
39+
// start++
40+
// end--
41+
// }
42+
// return true
43+
// }
44+
// }
45+
46+
// export default PalindromePartitioning
47+
48+
// use a function instead of class and reuse existing palindrome function not isPalindrome function
49+
50+
import{palindrome}from'./Palindrome'
51+
52+
constpartitionPalindrome=(s)=>{
53+
constresult=[]
54+
backtrack(s,[],result)
55+
returnresult
56+
}
57+
58+
constbacktrack=(s,path,result)=>{
59+
if(s.length===0){
60+
result.push([...path])
61+
return
62+
}
63+
64+
for(leti=0;i<s.length;i++){
65+
constprefix=s.substring(0,i+1)
66+
if(palindrome(prefix)){
67+
path.push(prefix)
68+
backtrack(s.substring(i+1),path,result)
69+
path.pop()
70+
}
71+
}
72+
}
73+
74+
exportdefaultpartitionPalindrome
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
importpartitionPalindromefrom'../PalindromePartitioning'
2+
3+
describe('Palindrome Partitioning',()=>{
4+
it('should return all possible palindrome partitioning of s',()=>{
5+
expect(partitionPalindrome('aab')).toEqual([
6+
['a','a','b'],
7+
['aa','b']
8+
])
9+
expect(partitionPalindrome('a')).toEqual([['a']])
10+
expect(partitionPalindrome('ab')).toEqual([['a','b']])
11+
})
12+
})

0 commit comments

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