This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1268 (Medium): Search Suggestions System
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given an array of strings
productsand a stringsearchWord. We want to design a system that suggests at most three product names fromproductsafter each character ofsearchWordis typed. Suggested products should have common prefix with thesearchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.Return list of lists of the suggested
productsafter each character ofsearchWordis typed.
Examples:
Example 1: Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse" Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]
Example 2: Input: products = ["havana"], searchWord = "havana" Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Example 3: Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags" Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
Example 4: Input: products = ["havana"], searchWord = "tatiana" Output: [[],[],[],[],[],[],[]]
Constraints:
1 <= products.length <= 1000- There are no repeated elements in
products.1 <= Σ products[i].length <= 2 * 10^4- All characters of
products[i]are lower-case English letters.1 <= searchWord.length <= 1000- All characters of
searchWordare lower-case English letters.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
Despite the fact that the clues suggest a binary search and a trie, the optimal solution to this problem needs neither. The substrings formed by adding one letter at a time from the search word (S) are naturally already in lexicographical order, as are the results that we're instructed to push into our answer array (ans).
So if we sort the products array (P), we should only ever need to iterate through P once during the entire remaining process of the solution with a time complexity of O(N). A single binary search would only require log(N) time, but we'd have to perform M = S.length binary searches, so in total they would take O(M * log(N)) time, compared to the O(N) time of a simple iteration.
With constraints of 1000 on both M and N, the binary search route would max out at a worse time complexity than iteration. Regardless, the sort itself, which is required for both, requires O(N * log(N)) time already, so neither option can decrease the overall time complexity required.
So in order to only require a single pass through P, we should keep track of the current bounds for the range of matches (left, right), then we'll iterate through the characters (c) of S. At each iteration, we'll first want to move left forward and right back to narrow the range of matches based on the new value of c.
Then we can add the next three elements of P to our result array (res), as long as they fall inside the range [left, right]. Once that's done, we can add res to ans and move to the next iteration.
Once we've finished iterating through S, we can return ans.
- Time Complexity: O(N * log(N)) where N is the length of P
- Space Complexity: O(1) excluding output space required for ans
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var suggestedProducts = function(P, S) {
P.sort()
let ans = [], left = 0, right = P.length - 1
for (let i = 0; i < S.length; i++) {
let c = S.charAt(i), res = []
while (P[left]?.charAt(i) < c) left++
while (P[right]?.charAt(i) > c) right--
for (let j = 0; j < 3 && left + j <= right; j++)
res.push(P[left+j])
ans.push(res)
}
return ans
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def suggestedProducts(self, P: List[str], S: str) -> List[List[str]]:
P.sort()
ans, left, right = [], 0, len(P) - 1
for i in range(len(S)):
c, res = S[i], []
while left <= right and (len(P[left]) == i or P[left][i] < c): left += 1
while left <= right and (len(P[right]) == i or P[right][i] > c): right -= 1
for j in range(3):
if left + j > right: break
else: res.append(P[left+j])
ans.append(res)
return ans
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public List<List<String>> suggestedProducts(String[] P, String S) {
Arrays.sort(P);
List<List<String>> ans = new ArrayList<>();
int left = 0, right = P.length - 1;
for (int i = 0; i < S.length(); i++) {
List<String> res = new ArrayList<>();
char c = S.charAt(i);
while (left <= right && (P[left].length() == i || P[left].charAt(i) < c)) left++;
while (left <= right && (P[right].length() == i || P[right].charAt(i) > c)) right--;
for (int j = 0; j < 3 && left + j <= right; j++)
res.add(P[left+j]);
ans.add(res);
}
return ans;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& P, string S) {
sort(P.begin(), P.end());
vector<vector<string>> ans;
int left = 0, right = P.size() - 1;
for (int i = 0; i < S.length(); i++) {
vector<string> res;
char c = S[i];
while (left <= right && (P[left].length() == i || P[left][i] < c)) left++;
while (left <= right && (P[right].length() == i || P[right][i] > c)) right--;
for (int j = 0; j < 3 && left + j <= right; j++)
res.push_back(P[left+j]);
ans.push_back(res);
}
return ans;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-05-31T11:49:34+00:00) Solution: Search Suggestions System. Retrieved from https://www.scien.cx/2021/05/31/solution-search-suggestions-system/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.