Commit90f9a00

committed

add a solution for 5

1 parent4ce5910 commit90f9a00Copy full SHA for 90f9a00

File tree

+37

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _5.java
- test/java/com/fishercoder
  - _5Test.java

+37

-0

lines changed

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -60,6 +60,40 @@ private int expand(String s, int left, int right) {`
`60`	`60`	`}`
`61`	`61`	`returnr -l -1;`
`62`	`62`	`}`
	`63`	`+ }`
	`64`	`+`
	`65`	`+publicstaticclassSolution3 {`
	`66`	`+/**`
	`67`	`+ * My own implementation using the same idea.`
	`68`	`+ */`
	`69`	`+publicStringlongestPalindrome(Strings) {`
	`70`	`+Stringans ="";`
	`71`	`+intmaxLen =0;`
	`72`	`+for (inti =0;i <s.length();i++) {`
	`73`	`+int[]pair =expand(s,i,i);`
	`74`	`+if (pair[1] -pair[0] +1 >maxLen) {`
	`75`	`+maxLen =pair[1] -pair[0] +1;`
	`76`	`+ans =s.substring(pair[0],pair[1] +1);`
	`77`	`+ }`
	`78`	`+pair =expand(s,i,i +1);`
	`79`	`+if (pair[1] -pair[0] +1 >maxLen) {`
	`80`	`+maxLen =pair[1] -pair[0] +1;`
	`81`	`+ans =s.substring(pair[0],pair[1] +1);`
	`82`	`+ }`
	`83`	`+ }`
	`84`	`+returnans;`
	`85`	`+ }`
	`86`	`+`
	`87`	`+privateint[]expand(Strings,intl,intr) {`
	`88`	`+int[]pair =newint[2];`
	`89`	`+while (l >=0 &&r <s.length() &&s.charAt(l) ==s.charAt(r)) {`
	`90`	`+pair[0] =l;`
	`91`	`+pair[1] =r;`
	`92`	`+l--;`
	`93`	`+r++;`
	`94`	`+ }`
	`95`	`+returnpair;`
	`96`	`+ }`
`63`	`97`
`64`	`98`	`}`
`65`	`99`	`}`

Lines changed: 3 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,19 +9,22 @@`
`9`	`9`	`publicclass_5Test {`
`10`	`10`	`privatestatic_5.Solution1solution1;`
`11`	`11`	`privatestatic_5.Solution2solution2;`
	`12`	`+privatestatic_5.Solution3solution3;`
`12`	`13`	`privatestaticStrings;`
`13`	`14`
`14`	`15`	`@BeforeClass`
`15`	`16`	`publicstaticvoidsetup() {`
`16`	`17`	`solution1 =new_5.Solution1();`
`17`	`18`	`solution2 =new_5.Solution2();`
	`19`	`+solution3 =new_5.Solution3();`
`18`	`20`	`}`
`19`	`21`
`20`	`22`	`@Test`
`21`	`23`	`publicvoidtest1() {`
`22`	`24`	`s ="babad";`
`23`	`25`	`assertEquals("bab",solution1.longestPalindrome(s));`
`24`	`26`	`assertEquals("aba",solution2.longestPalindrome(s));`
	`27`	`+assertEquals("aba",solution3.longestPalindrome(s));`
`25`	`28`	`}`
`26`	`29`
`27`	`30`	`}`

Comments

(0)