forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAnagrams.java
More file actions
executable file
·142 lines (121 loc) · 4.35 KB
/
Anagrams.java
File metadata and controls
executable file
·142 lines (121 loc) · 4.35 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
M
1531455963
tags: Array, Hash Table
把anagram找到并output
#### HashMap
- 存在int[26], Arrays.toString(arr) 就是 string key: character frequency map
- anagram都有一样的key, 存进hashmap<string, list of anagrams>
- output anagrams
#### HashMap + Sort
- HashMap 的做法. sort每个string, 存进HashMap, 重复的就是anagrams,最后输出。
- toCharArray
- Arrays.sort
- Stirng.valueOf(char[])
- 时间n*L*O(logL),L是最长string的长度。
#### Previous Notes
- Arrays.toString(arr)的做法。arr是int[26], assuming only have 26 lowercase letters.
- Count occurrance, 然后convert to String，作为map的key.
- Time complexity: nO(L)
- 另一种做法：http://www.jiuzhang.com/solutions/anagrams/
- 1. take each string, count the occurrance of the 26 letters. save in int[]count.
- 2. hash the int[] count and output a unique hash value; hash = hash * a + num; a = a * b.
- 3. save to hashmap in the same way as we do.
- 这一步把for s: strs 里面的时间复杂度降到了O(L). L = s.length().
- Need to work on the getHash() function.
- 时间变成n*O(L). Better.
```
/*
LintCode
Given an array of strings, return all groups of strings that are anagrams.
Example
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].
Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
Note
All inputs will be in lower-case
Tags Expand
String Hash Table
*/
public class Solution {
public List<String> anagrams(String[] strs) {
List<String> rst = new ArrayList<>();
if (strs == null || strs == null) return rst;
Map<String, List<String>> map = new HashMap<>();
for (String word : strs){
int[] arr = new int[26];
for (char c : word.toCharArray()) arr[c - 'a']++;
String key = Arrays.toString(arr);
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(word);
}
for (List<String> list : map.values()) {
if (list.size() >= 2) rst.addAll(list);
}
return rst;
}
}
/*
//2.29.2016
use int[26] assuming it's all lowercase letters
count each string char in a letter array int[], convert the array into string.
HashMap carray string as key, and actualy string as value
outupt all values
*/
public class Solution {
public List<String> anagrams(String[] strs) {
List<String> rst = new ArrayList<String>();
if (strs == null || strs.length == 0) {
return rst;
}
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
for (int i = 0; i < strs.length; i++) {
int[] arr = new int[26];
for (int j = 0; j < strs[i].length(); j++) {
arr[strs[i].charAt(j) - 'a'] += 1;
}
String arrString = Arrays.toString(arr);
if (!map.containsKey(arrString)) {
map.put(arrString, new ArrayList<String>());
}
map.get(arrString).add(strs[i]);
}
//Output
for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) {
if (entry.getValue().size() >= 2)
rst.addAll(entry.getValue());
}
return rst;
}
}
/*
Recap 12.09.2015
Feels like put into a hashmap of each string's sorted version. <String, ArrayList<Sting>>
compare each string. If match, add into it.
reurn all that has >= 2 items
*/
public class Solution {
public List<String> anagrams(String[] strs) {
List<String> rst = new ArrayList<String>();
if (strs == null || strs.length == 0) {
return rst;
}
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
for (int i = 0; i < strs.length; i++) {
char[] arr = strs[i].toCharArray();
Arrays.sort(arr);
String s = String.valueOf(arr);
if (!map.containsKey(s)) {
ArrayList<String> list = new ArrayList<String>();
map.put(s, list);
}
map.get(s).add(strs[i]);
}
//check instance occurs >= 2
for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) {
if (entry.getValue().size() >= 2) {
rst.addAll(entry.getValue());
}
}
return rst;
}
}
```