Commit4604148

committed

add a solution for 567

1 parentbcde39a commit4604148Copy full SHA for 4604148

File tree

+55

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _567.java
- test/java/com/fishercoder
  - _567Test.java

+55

-0

lines changed

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -43,4 +43,46 @@ private boolean allZeroes(int[] count) {`
`43`	`43`	`returntrue;`
`44`	`44`	`}`
`45`	`45`	`}`
	`46`	`+`
	`47`	`+publicstaticclassSolution2 {`
	`48`	`+/**`
	`49`	`+ * A classic sliding window problem.`
	`50`	`+ * I came up with below solution independently on 9/17/2021.`
	`51`	`+ * <p>`
	`52`	`+ * A few pointers that led me to the sliding window approach:`
	`53`	`+ * 1. if it's a valid permutation, the substring from S2 must have equal length as of s1;`
	`54`	`+ * 2. I don't want to repeatedly calculate each and every possible substring of s2, if s1 is really long, this could mean lots of redundant calculation.`
	`55`	`+ * So sliding window to the rescue!`
	`56`	`+ */`
	`57`	`+publicbooleancheckInclusion(Strings1,Strings2) {`
	`58`	`+if (s1.length() >s2.length()) {`
	`59`	`+returnfalse;`
	`60`	`+ }`
	`61`	`+int[]count =newint[26];`
	`62`	`+for (charc :s1.toCharArray()) {`
	`63`	`+count[c -'a']++;`
	`64`	`+ }`
	`65`	`+for (inti =0;i <s1.length();i++) {`
	`66`	`+count[s2.charAt(i) -'a']--;`
	`67`	`+ }`
	`68`	`+for (inti =s1.length(),j =0;i <s2.length();i++,j++) {`
	`69`	`+if (isPermutation(count)) {`
	`70`	`+returntrue;`
	`71`	`+ }else {`
	`72`	`+count[s2.charAt(j) -'a']++;`
	`73`	`+count[s2.charAt(i) -'a']--;`
	`74`	`+ }`
	`75`	`+ }`
	`76`	`+returnisPermutation(count);`
	`77`	`+ }`
	`78`	`+`
	`79`	`+privatebooleanisPermutation(int[]count) {`
	`80`	`+for (intc :count) {`
	`81`	`+if (c !=0) {`
	`82`	`+returnfalse;`
	`83`	`+ }`
	`84`	`+ }`
	`85`	`+returntrue;`
	`86`	`+ }`
	`87`	`+ }`
`46`	`88`	`}`

Lines changed: 13 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,6 +8,7 @@`
`8`	`8`
`9`	`9`	`publicclass_567Test {`
`10`	`10`	`privatestatic_567.Solution1solution1;`
	`11`	`+privatestatic_567.Solution2solution2;`
`11`	`12`	`privatestaticbooleanexpected;`
`12`	`13`	`privatestaticbooleanactual;`
`13`	`14`	`privatestaticStrings1;`
`@@ -16,6 +17,7 @@ public class _567Test {`
`16`	`17`	`@BeforeClass`
`17`	`18`	`publicstaticvoidsetup() {`
`18`	`19`	`solution1 =new_567.Solution1();`
	`20`	`+solution2 =new_567.Solution2();`
`19`	`21`	`}`
`20`	`22`
`21`	`23`	`@Test`
`@@ -24,6 +26,17 @@ public void test1() {`
`24`	`26`	`s2 ="eidbaooo";`
`25`	`27`	`expected =true;`
`26`	`28`	`actual =solution1.checkInclusion(s1,s2);`
	`29`	`+actual =solution2.checkInclusion(s1,s2);`
	`30`	`+assertEquals(expected,actual);`
	`31`	`+ }`
	`32`	`+`
	`33`	`+@Test`
	`34`	`+publicvoidtest2() {`
	`35`	`+s1 ="adc";`
	`36`	`+s2 ="dcda";`
	`37`	`+expected =true;`
	`38`	`+actual =solution1.checkInclusion(s1,s2);`
	`39`	`+actual =solution2.checkInclusion(s1,s2);`
`27`	`40`	`assertEquals(expected,actual);`
`28`	`41`	`}`
`29`	`42`	`}`

Comments

(0)