-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
819.java
65 lines (62 loc) · 2.31 KB
/
819.java
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
__________________________________________________________________________________________________
sample 2 ms submission
class Solution {
public String mostCommonWord(String paragraph, String[] banned) {
Trie root = new Trie();
Trie curr= root;
for(String ban:banned){
for(int i=0;i<ban.length();i++){
int idx = ban.charAt(i)-'a';
if(curr.next[idx]==null){
curr.next[idx]=new Trie();
}
curr=curr.next[idx];
}
curr.banned=true;
curr= root;
}
paragraph = paragraph.toLowerCase();
int maxCount=0;
String mostFrequent="";
char[] pArray = paragraph.toCharArray();
for(int i=0,j=0;i<pArray.length;i=j+1){
while(i<pArray.length && (pArray[i]<'a' || pArray[i]>'z')) i++;
for(j=i;j<pArray.length && (pArray[j]>='a'&& pArray[j]<='z');j++){
int idx = pArray[j]-'a';
if(curr.next[idx]==null){
curr.next[idx]=new Trie();
}
curr=curr.next[idx];
}
if(curr!=root && !curr.banned){
curr.count++;
if(curr.count>maxCount){
mostFrequent= paragraph.substring(i,j);
maxCount++;
}
}
curr=root;
}
return mostFrequent;
}
class Trie{
Trie[] next = new Trie[26];
int count;
boolean banned=false;
}
}
__________________________________________________________________________________________________
sample 34680 kb submission
class Solution {
public String mostCommonWord(String paragraph, String[] banned) {
if (paragraph == null || banned == null) return "";
Set<String> ban = new HashSet<>(Arrays.asList(banned));
String[] words = paragraph.toLowerCase().split("\\W+");
Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
if (!ban.contains(word)) freq.put(word, freq.getOrDefault(word, 0) + 1);
}
return Collections.max(freq.entrySet(), Map.Entry.comparingByValue()).getKey();
}
}
__________________________________________________________________________________________________