Commit4bdaa5c

committed

Implemented Palindrome Partitioning using Backtracking algorithm

1 parent39d0113 commit4bdaa5cCopy full SHA for 4bdaa5c

File tree

+75

-0

lines changed

+75

-0

lines changed

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`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`	`+classPalindromePartitioning{`
	`10`	`+partition(s){`
	`11`	`+constresult=[]`
	`12`	`+this.backtrack(s,[],result)`
	`13`	`+returnresult`
	`14`	`+}`
	`15`	`+`
	`16`	`+backtrack(s,path,result){`
	`17`	`+if(s.length===0){`
	`18`	`+result.push([...path])`
	`19`	`+return`
	`20`	`+}`
	`21`	`+`
	`22`	`+for(leti=0;i<s.length;i++){`
	`23`	`+constprefix=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`	`+letstart=0`
	`34`	`+letend=s.length-1`
	`35`	`+while(start<end){`
	`36`	`+if(s.charAt(start)!==s.charAt(end)){`
	`37`	`+returnfalse`
	`38`	`+}`
	`39`	`+start++`
	`40`	`+end--`
	`41`	`+}`
	`42`	`+returntrue`
	`43`	`+}`
	`44`	`+}`
	`45`	`+`
	`46`	`+exportdefaultPalindromePartitioning`

Lines changed: 29 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,29 @@`
	`1`	`+importPalindromePartitioningfrom'../PalindromePartitioning'`
	`2`	`+`
	`3`	`+describe('PalindromePartitioning',()=>{`
	`4`	`+it('should partition a string into palindromes',()=>{`
	`5`	`+constpp=newPalindromePartitioning()`
	`6`	`+constresult=pp.partition('aab')`
	`7`	`+`
	`8`	`+expect(result).toEqual(`
	`9`	`+expect.arrayContaining([`
	`10`	`+['a','a','b'],`
	`11`	`+['aa','b']`
	`12`	`+])`
	`13`	`+)`
	`14`	`+})`
	`15`	`+`
	`16`	`+it('should handle empty string',()=>{`
	`17`	`+constpp=newPalindromePartitioning()`
	`18`	`+constresult=pp.partition('')`
	`19`	`+`
	`20`	`+expect(result).toEqual([[]])`
	`21`	`+})`
	`22`	`+`
	`23`	`+it('should handle a single character string',()=>{`
	`24`	`+constpp=newPalindromePartitioning()`
	`25`	`+constresult=pp.partition('c')`
	`26`	`+`
	`27`	`+expect(result).toEqual([['c']])`
	`28`	`+})`
	`29`	`+})`

Comments

(0)