Commitcff8014

committed

add a solution for 76

1 parentb5c9395 commitcff8014Copy full SHA for cff8014

File tree

+77

-10

lines changed

src
- main/java/com/fishercoder/solutions
  - _76.java
- test/java/com/fishercoder
  - _76Test.java

+77

-10

lines changed

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -41,4 +41,45 @@ public String minWindow(String s, String t) {`
`41`	`41`	`returns.substring(minStart,minStart +minLen);`
`42`	`42`	`}`
`43`	`43`	`}`
	`44`	`+`
	`45`	`+publicstaticclassSolution2 {`
	`46`	`+/**`
	`47`	`+ * I implemented below solution on my own following the hints on LeetCode.`
	`48`	`+ * In comparison, Solution1 is more optimized and runs faster.`
	`49`	`+ */`
	`50`	`+publicStringminWindow(Strings,Stringt) {`
	`51`	`+if (t.length() >s.length()) {`
	`52`	`+return"";`
	`53`	`+ }`
	`54`	`+int[]tCount =newint[256];`
	`55`	`+for (inti =0;i <t.length();i++) {`
	`56`	`+tCount[t.charAt(i)]++;`
	`57`	`+ }`
	`58`	`+intleft =0;`
	`59`	`+intright =0;`
	`60`	`+int[]sCount =newint[256];`
	`61`	`+Stringans ="";`
	`62`	`+while (right <s.length()) {`
	`63`	`+sCount[s.charAt(right)]++;`
	`64`	`+while (isValid(sCount,tCount)) {`
	`65`	`+if (right -left <ans.length() \|\|ans.equals("")) {`
	`66`	`+ans =s.substring(left,right +1);`
	`67`	`+ }`
	`68`	`+sCount[s.charAt(left)]--;`
	`69`	`+left++;`
	`70`	`+ }`
	`71`	`+right++;`
	`72`	`+ }`
	`73`	`+returnans;`
	`74`	`+ }`
	`75`	`+`
	`76`	`+privatebooleanisValid(int[]sCount,int[]tCount) {`
	`77`	`+for (inti =0;i <sCount.length;i++) {`
	`78`	`+if (sCount[i] <tCount[i]) {`
	`79`	`+returnfalse;`
	`80`	`+ }`
	`81`	`+ }`
	`82`	`+returntrue;`
	`83`	`+ }`
	`84`	`+ }`
`44`	`85`	`}`

Lines changed: 36 additions & 10 deletions

Original file line number	Diff line number	Diff line change
`@@ -7,16 +7,42 @@`
`7`	`7`	`importstaticorg.junit.Assert.assertEquals;`
`8`	`8`
`9`	`9`	`publicclass_76Test {`
`10`		`-privatestatic_76.Solution1solution1;`
`11`		`-privatestaticint[]nums;`
	`10`	`+privatestatic_76.Solution1solution1;`
	`11`	`+privatestatic_76.Solution2solution2;`
	`12`	`+privatestaticStringexpected;`
	`13`	`+privatestaticStrings;`
	`14`	`+privatestaticStringt;`
`12`	`15`
`13`		`-@BeforeClass`
`14`		`-publicstaticvoidsetup() {`
`15`		`-solution1 =new_76.Solution1();`
`16`		`- }`
	`16`	`+@BeforeClass`
	`17`	`+publicstaticvoidsetup() {`
	`18`	`+solution1 =new_76.Solution1();`
	`19`	`+solution2 =new_76.Solution2();`
	`20`	`+ }`
`17`	`21`
`18`		`-@Test`
`19`		`-publicvoidtest1() {`
`20`		`-assertEquals("BANC",solution1.minWindow("ADOBECODEBANC","ABC"));`
`21`		`- }`
	`22`	`+@Test`
	`23`	`+publicvoidtest1() {`
	`24`	`+expected ="BANC";`
	`25`	`+s ="ADOBECODEBANC";`
	`26`	`+t ="ABC";`
	`27`	`+assertEquals(expected,solution1.minWindow(s,t));`
	`28`	`+assertEquals(expected,solution2.minWindow(s,t));`
	`29`	`+ }`
	`30`	`+`
	`31`	`+@Test`
	`32`	`+publicvoidtest2() {`
	`33`	`+expected ="";`
	`34`	`+s ="A";`
	`35`	`+t ="B";`
	`36`	`+assertEquals(expected,solution1.minWindow(s,t));`
	`37`	`+assertEquals(expected,solution2.minWindow(s,t));`
	`38`	`+ }`
	`39`	`+`
	`40`	`+@Test`
	`41`	`+publicvoidtest3() {`
	`42`	`+expected ="cwae";`
	`43`	`+s ="cabwefgewcwaefgcf";`
	`44`	`+t ="cae";`
	`45`	`+assertEquals(expected,solution1.minWindow(s,t));`
	`46`	`+assertEquals(expected,solution2.minWindow(s,t));`
	`47`	`+ }`
`22`	`48`	`}`

Comments

(0)