1268. Search Suggestions System
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
int begin = 0;
int end = products.length - 1;
List<List<String>> result = new ArrayList<List<String>>();
for (int i = 0; i < searchWord.length(); i++) {
List<String> words = new ArrayList<String>();
char c = searchWord.charAt(i);
while (begin <= end && (products[begin].length() <= i ||
products[begin].charAt(i) != c)) {
begin++;
}
while (begin <= end && (products[end].length() <= i ||
products[end].charAt(i) != c)) {
end--;
}
int howfar = Math.min(end+1, begin + 3);
for (int l = begin; l < howfar; l++) {
words.add(products[l]);
}
result.add(words);
}
return result;
}
}Runtime: 6 ms, faster than 99.85% of Java online submissions for Search Suggestions System.
Memory Usage: 44.7 MB, less than 78.10% of Java online submissions for Search Suggestions System.
처음에 sort를 해주면 uri가 봐야하는 부분은 한정되어 있다는 점을 이용해서
연관이 있는 첫부분과 끝부분만 조졌읍니다~~
처음에는 trie를 쓰려고 했는데..... 넘 어려울거 같더라구요
// Custom class Trie with function to get 3 words starting with given prefix
class Trie {
// Node definition of a trie
class Node {
boolean isWord = false;
List<Node> children = Arrays.asList(new Node[26]);
};
Node Root, curr;
List<String> resultBuffer;
// Runs a DFS on trie starting with given prefix and adds all the words in the resultBuffer, limiting result size to 3
void dfsWithPrefix(Node curr, String word) {
if (resultBuffer.size() == 3)
return;
if (curr.isWord)
resultBuffer.add(word);
// Run DFS on all possible paths.
for (char c = 'a'; c <= 'z'; c++)
if (curr.children.get(c - 'a') != null)
dfsWithPrefix(curr.children.get(c - 'a'), word + c);
}
Trie() {
Root = new Node();
}
// Inserts the string in trie.
void insert(String s) {
// Points curr to the root of trie.
curr = Root;
for (char c : s.toCharArray()) {
if (curr.children.get(c - 'a') == null)
curr.children.set(c - 'a', new Node());
curr = curr.children.get(c - 'a');
}
// Mark this node as a completed word.
curr.isWord = true;
}
List<String> getWordsStartingWith(String prefix) {
curr = Root;
resultBuffer = new ArrayList<String>();
// Move curr to the end of prefix in its trie representation.
for (char c : prefix.toCharArray()) {
if (curr.children.get(c - 'a') == null)
return resultBuffer;
curr = curr.children.get(c - 'a');
}
dfsWithPrefix(curr, prefix);
return resultBuffer;
}
};
class Solution {
List<List<String>> suggestedProducts(String[] products,
String searchWord) {
Trie trie = new Trie();
List<List<String>> result = new ArrayList<>();
// Add all words to trie.
for (String w : products)
trie.insert(w);
String prefix = new String();
for (char c : searchWord.toCharArray()) {
prefix += c;
result.add(trie.getWordsStartingWith(prefix));
}
return result;
}
};Runtime: 146 ms, faster than 16.46% of Java online submissions for Search Suggestions System.
Memory Usage: 48 MB, less than 53.16% of Java online submissions for Search Suggestions System.
Trie & DFS 루션이
Trie를 만들어주고 (핵심: boolean isWord와 List children);
DFS로 단어를 찾아주는 방식...
보기만 해도 머리가 아파요;
1152. Analyze User Website Visit Pattern
class Solution {
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
Map<String, HashMap<String>> m = new HashMap<String, HashMap<String>>();
for (int i = 0; i < username.length; i++) {
map.put(username[i], m.get)
}
}
}2번 문제에 모든 열과성을 다했다는점...^^
아이디어는 String, HashMap 쉬맵이를 만들어 준 다음에
검색어 - 검색한 사람, 검색한 횟수를 잡아주려고 했는데
지금 생각해보니깐 이래저래 애로사항이 많네요^^..
루션이
class Pair {
int time;
String web;
public Pair(int time, String web) {
this.time = time;
this.web = web;
}
}
class Solution {
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
Map<String, List<Pair>> map = new HashMap<>();
int n = username.length;
// collect the website info for every user, key: username, value: (timestamp, website)
for (int i = 0; i < n; i++) {
map.putIfAbsent(username[i], new ArrayList<>());
map.get(username[i]).add(new Pair(timestamp[i], website[i]));
}
// count map to record every 3 combination occuring time for the different user.
Map<String, Integer> count = new HashMap<>();
String res = "";
for (String key : map.keySet()) {
Set<String> set = new HashSet<>();
// this set is to avoid visit the same 3-seq in one user
List<Pair> list = map.get(key);
Collections.sort(list, (a, b)->(a.time - b.time)); // sort by time
// brutal force O(N ^ 3)
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
for (int k = j + 1; k < list.size(); k++) {
String str = list.get(i).web + " " + list.get(j).web + " " + list.get(k).web;
if (!set.contains(str)) {
count.put(str, count.getOrDefault(str, 0) + 1);
set.add(str);
}
if (res.equals("") || count.get(res) < count.get(str) || (count.get(res) == count.get(str) && res.compareTo(str) > 0)) {
// make sure the right lexi order
res = str;
}
}
}
}
}
// grab the right answer
String[] r = res.split(" ");
List<String> result = new ArrayList<>();
for (String str : r) {
result.add(str);
}
return result;
}
}Runtime: 32 ms, faster than 29.05% of Java online submissions for Analyze User Website Visit Pattern.
Memory Usage: 40.1 MB, less than 50.37% of Java online submissions for Analyze User Website Visit Pattern.
제가 쉬맵이로 하려던걸 Pair로 하네요
저도 앞으로는 pair을 적극 활용해보겠읍니다...^^
근데 3중포문이 실화냐...
전씨를 위한 평이 좋은 이선이 루션~~
class Solution:
def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
# Create tuples as shown in description
# The timestamps may not always be pre-ordered (one of the testcases)
# Sort first based on user, then time (grouping by user)
# This also helps to maintain order of websites visited in the later part of the solution
users = defaultdict(list)
# It is not necessary to use defaultdict here, we can manually create dictionaries too
for user, time, site in sorted(zip(username, timestamp, website), key = lambda x: (x[0],x[1])):
users[user].append(site) # defaultdicts simplify and optimize code
patterns = Counter() # this can also be replaced with a manually created dictionary of counts
# Get unique 3-sequence (note that website order will automatically be maintained)
# Note that we take the set of each 3-sequence for each user as they may have repeats
# For each 3-sequence, count number of users
for user, sites in users.items():
patterns.update(Counter(set(combinations(sites, 3))))
# Re-iterating above step for clarity
# 1. first get all possible 3-sequences combinations(sites, 3)
# 2. then, count each one once (set)
# 3. finally, count the number of times we've seen the 3-sequence for every user (patterns.update(Counter))
# - updating a dictionary will update the value for existing keys accordingly (int in this case)
# An expanded version of the above step is given below.
# print(patterns) # sanity check
# get most frequent 3-sequence sorted lexicographically
return max(sorted(patterns), key=patterns.get)Runtime: 52 ms, faster than 66.84% of Python3 online submissions for Analyze User Website Visit Pattern.
Memory Usage: 14.7 MB, less than 62.58% of Python3 online submissions for Analyze User Website Visit Pattern.
TMI: 이거 루션이 쓰신 분도 백수시라네요
y