Commitca1c5dc

applewjg

committed

Palindrome Partition I && II

Change-Id: I30f8b3147f6a89739508c58e13c78347a3ae0dc1

1 parent0d217c6 commitca1c5dcCopy full SHA for ca1c5dc

File tree

+78

-0

lines changed

+78

-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`	`+ Author: Andy, nkuwjg@gmail.com`
	`3`	`+ Date: Jan 20, 2015`
	`4`	`+ Problem: Palindrome Partitioning`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/palindrome-partitioning/`
	`7`	`+ Notes:`
	`8`	`+ Given a string s, partition s such that every substring of the partition is a palindrome.`
	`9`	`+ Return all possible palindrome partitioning of s.`
	`10`	`+ For example, given s = "aab",`
	`11`	`+ Return`
	`12`	`+ [`
	`13`	`+ ["aa","b"],`
	`14`	`+ ["a","a","b"]`
	`15`	`+ ]`
	`16`	`+`
	`17`	`+ Solution: ...`
	`18`	`+ */`
	`19`	`+`
	`20`	`+publicclassSolution {`
	`21`	`+publicList<List<String>>partition(Strings) {`
	`22`	`+List<List<String>>res =newArrayList<List<String>>();`
	`23`	`+intn =s.length();`
	`24`	`+boolean[][]dp =newboolean[n][n];`
	`25`	`+for (inti =n -1;i >=0; --i) {`
	`26`	`+for (intj =i;j <n; ++j) {`
	`27`	`+dp[i][j]=(s.charAt(i)==s.charAt(j))&&(j<i+2\|\|dp[i+1][j-1]);`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+ArrayList<String>path =newArrayList<String>();`
	`31`	`+dfs(s,dp,0,path,res);`
	`32`	`+returnres;`
	`33`	`+ }`
	`34`	`+publicvoiddfs(Strings,boolean[][]dp,intstart,ArrayList<String>path,List<List<String>>res) {`
	`35`	`+if (s.length() ==start) {`
	`36`	`+res.add(newArrayList<String>(path));`
	`37`	`+return;`
	`38`	`+ }`
	`39`	`+for (inti =start;i <s.length(); ++i) {`
	`40`	`+if (dp[start][i] ==false)continue;`
	`41`	`+path.add(s.substring(start,i+1));`
	`42`	`+dfs(s,dp,i+1,path,res);`
	`43`	`+path.remove(path.size()-1);`
	`44`	`+ }`
	`45`	`+ }`
	`46`	`+}`

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,32 @@`
	`1`	`+/*`
	`2`	`+ Author: Andy, nkuwjg@gmail.com`
	`3`	`+ Date: Jan 23, 2015`
	`4`	`+ Problem: Palindrome Partitioning II`
	`5`	`+ Difficulty: Hard`
	`6`	`+ Source: https://oj.leetcode.com/problems/palindrome-partitioning-ii/`
	`7`	`+ Notes:`
	`8`	`+ Given a string s, partition s such that every substring of the partition is a palindrome.`
	`9`	`+ Return the minimum cuts needed for a palindrome partitioning of s.`
	`10`	`+ For example, given s = "aab",`
	`11`	`+ Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.`
	`12`	`+`
	`13`	`+ Solution: dp.`
	`14`	`+ */`
	`15`	`+publicclassSolution {`
	`16`	`+publicintminCut(Strings) {`
	`17`	`+intn =s.length();`
	`18`	`+int[]dp =newint[n+1];`
	`19`	`+dp[n] = -1;`
	`20`	`+boolean[][]isP =newboolean[n][n];`
	`21`	`+for (inti =n -1;i >=0; --i) {`
	`22`	`+dp[i] =n -1 -i;`
	`23`	`+for (intj =i;j <n; ++j) {`
	`24`	`+if (s.charAt(i) ==s.charAt(j) && (j <i +2 \|\|isP[i+1][j-1]))isP[i][j] =true;`
	`25`	`+if (isP[i][j] ==true) {`
	`26`	`+dp[i] =Math.min(dp[i],1 +dp[j+1]);`
	`27`	`+ }`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+returndp[0];`
	`31`	`+ }`
	`32`	`+}`

Comments

(0)