Commit8a0992a

committed

add 1745

1 parent8206625 commit8a0992aCopy full SHA for 8a0992a

File tree

+73

-0

lines changed

README.md
src
- main/java/com/fishercoder/solutions
  - _1745.java
- test/java/com/fishercoder
  - _1745Test.java

+73

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★`
`8`	`8`
`9`	`9`	`\| # \| Title \| Solutions \| Video \| Difficulty \| Tag`
`10`	`10`	`\|-----\|----------------\|---------------\|--------\|-------------\|-------------`
	`11`	`+\|1745\|[Palindrome Partitioning IV](https://leetcode.com/problems/palindrome-partitioning-iv/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1745.java)\|\|Hard\|String, DP\|`
`11`	`12`	`\|1743\|[Restore the Array From Adjacent Pairs](https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1743.java)\|\|Medium\|Greedy\|`
`12`	`13`	`\|1742\|[Maximum Number of Balls in a Box](https://leetcode.com/problems/maximum-number-of-balls-in-a-box/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1742.java)\|\|Easy\|Array\|`
`13`	`14`	`\|1736\|[Latest Time by Replacing Hidden Digits](https://leetcode.com/problems/latest-time-by-replacing-hidden-digits/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_1736.java)\|\|Easy\|String, Greedy\|`

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,36 @@`
	`1`	`+packagecom.fishercoder.solutions;`
	`2`	`+`
	`3`	`+publicclass_1745 {`
	`4`	`+publicstaticclassSolution1 {`
	`5`	`+/**`
	`6`	`+ * credit: https://leetcode.com/problems/palindrome-partitioning-iv/discuss/1042910/Java-Detailed-Explanation-DP-O(N2)`
	`7`	`+ *`
	`8`	`+ * check whether substring(i, j) is a palindrome becomes checking whether substring(i + 1, j -1) is a palindrome`
	`9`	`+ *`
	`10`	`+ * How we build the dp array:`
	`11`	`+ * start from the top right of this square matrix`
	`12`	`+ */`
	`13`	`+publicbooleancheckPartitioning(Strings) {`
	`14`	`+intn =s.length();`
	`15`	`+boolean[][]dp =newboolean[n][n];`
	`16`	`+for (inti =n -1;i >=0;i--) {`
	`17`	`+for (intj =i;j <n;j++) {`
	`18`	`+if (s.charAt(i) ==s.charAt(j)) {`
	`19`	`+dp[i][j] = (i +1 <j -1) ?dp[i +1][j -1] :true;`
	`20`	`+ }else {`
	`21`	`+dp[i][j] =false;`
	`22`	`+ }`
	`23`	`+ }`
	`24`	`+ }`
	`25`	`+for (inti =1;i <n -1;i++) {`
	`26`	`+for (intj =1;j <n -1;j++) {`
	`27`	`+if (dp[0][i -1] &&dp[i][j] &&dp[j +1][n -1]) {`
	`28`	`+returntrue;`
	`29`	`+ }`
	`30`	`+ }`
	`31`	`+ }`
	`32`	`+returntrue;`
	`33`	`+ }`
	`34`	`+`
	`35`	`+ }`
	`36`	`+}`

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,36 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.solutions._1745;`
	`4`	`+importorg.junit.BeforeClass;`
	`5`	`+importorg.junit.Test;`
	`6`	`+`
	`7`	`+importstaticorg.junit.Assert.assertEquals;`
	`8`	`+`
	`9`	`+publicclass_1745Test {`
	`10`	`+privatestatic_1745.Solution1solution1;`
	`11`	`+`
	`12`	`+@BeforeClass`
	`13`	`+publicstaticvoidsetup() {`
	`14`	`+solution1 =new_1745.Solution1();`
	`15`	`+ }`
	`16`	`+`
	`17`	`+@Test`
	`18`	`+publicvoidtest1() {`
	`19`	`+assertEquals(true,solution1.checkPartitioning("abcbdd"));`
	`20`	`+ }`
	`21`	`+`
	`22`	`+@Test`
	`23`	`+publicvoidtest2() {`
	`24`	`+assertEquals(false,solution1.checkPartitioning("bcbddxy"));`
	`25`	`+ }`
	`26`	`+`
	`27`	`+@Test`
	`28`	`+publicvoidtest3() {`
	`29`	`+assertEquals(true,solution1.checkPartitioning("juchzcedhfesefhdeczhcujzzvbmoeombv"));`
	`30`	`+ }`
	`31`	`+`
	`32`	`+@Test`
	`33`	`+publicvoidtest4() {`
	`34`	`+assertEquals(true,solution1.checkPartitioning("gbofdldvwelqiizbievfolrujxnwjmjwsjrjeqecwssgtlteltslfzkblzihcgwjnqaiqbxohcnxulxozzkanaofgoddogfoanakzzoxluxnchoxbqiaqnjwgchizlbkzflstletltgsswceqejrjswjmjwnxjurlofveibziiqlewvdldfobgxebrcrbexv"));`
	`35`	`+ }`
	`36`	`+}`

Comments

(0)