Commitf64721e

committed

add a solution for 49

1 parent645684b commitf64721eCopy full SHA for f64721e

File tree

+30

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _49.java
- test/java/com/fishercoder
  - _49Test.java

+30

-0

lines changed

Lines changed: 29 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,6 +9,9 @@`
`9`	`9`	`publicclass_49 {`
`10`	`10`
`11`	`11`	`publicstaticclassSolution1 {`
	`12`	`+/**`
	`13`	`+ * Time: O(nklogk) where n is the # of strings in the given input and k is the maximum length of each string`
	`14`	`+ */`
`12`	`15`	`publicList<List<String>>groupAnagrams(String[]strs) {`
`13`	`16`	`Map<String,List<String>>map =newHashMap<>();`
`14`	`17`	`for (Stringword :strs) {`
`@@ -23,4 +26,30 @@ public List<List<String>> groupAnagrams(String[] strs) {`
`23`	`26`	`returnnewArrayList<>(map.values());`
`24`	`27`	`}`
`25`	`28`	`}`
	`29`	`+`
	`30`	`+publicstaticclassSolution2 {`
	`31`	`+/**`
	`32`	`+ * This is an improvement to the above solution in terms of time complexity.`
	`33`	`+ * Time: O(n*k) where n is the # of strings in the given input and k is the maximum length of each string`
	`34`	`+ */`
	`35`	`+publicList<List<String>>groupAnagrams(String[]strs) {`
	`36`	`+Map<String,List<String>>map =newHashMap<>();`
	`37`	`+for (Stringword :strs) {`
	`38`	`+int[]count =newint[26];`
	`39`	`+for (charc :word.toCharArray()) {`
	`40`	`+count[c -'a']++;`
	`41`	`+ }`
	`42`	`+StringBuildersb =newStringBuilder();`
	`43`	`+for (intc :count) {`
	`44`	`+sb.append(c);`
	`45`	`+sb.append("$");`
	`46`	`+ }`
	`47`	`+if (!map.containsKey(sb.toString())) {`
	`48`	`+map.put(sb.toString(),newArrayList<>());`
	`49`	`+ }`
	`50`	`+map.get(sb.toString()).add(word);`
	`51`	`+ }`
	`52`	`+returnnewArrayList<>(map.values());`
	`53`	`+ }`
	`54`	`+ }`
`26`	`55`	`}`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -12,6 +12,7 @@`
`12`	`12`
`13`	`13`	`importstaticjunit.framework.TestCase.assertEquals;`
`14`	`14`	`importstaticjunit.framework.TestCase.assertTrue;`
	`15`	`+importstaticorg.assertj.core.api.Assertions.assertThat;`
`15`	`16`
`16`	`17`	`publicclass_49Test {`
`17`	`18`	`privatestatic_49.Solution1solution1;`

Comments

(0)