Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Biweekly Contest 68 LeetCode Solution
Problem 1 – Maximum Number of Words Found in Sentences LeetCode Solution
A sentence is a list of words that are separated by a single space with no leading or trailing spaces.
You are given an array of strings sentences, where each sentences[i] represents a single sentence.
Return the maximum number of words that appear in a single sentence.
Example 1:
Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation:
- The first sentence, "alice and bob love leetcode", has 5 words in total.
- The second sentence, "i think so too", has 4 words in total.
- The third sentence, "this is great thanks very much", has 6 words in total.
Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.
Example 2:
Input: sentences = ["please wait", "continue to fight", "continue to win"]
Output: 3
Explanation: It is possible that multiple sentences contain the same number of words.
In this example, the second and third sentences (underlined) have the same number of words.
Constraints:
1 <= sentences.length <= 1001 <= sentences[i].length <= 100sentences[i]consists only of lowercase English letters and' 'only.sentences[i]does not have leading or trailing spaces.- All the words in
sentences[i]are separated by a single space.
Maximum Number of Words Found in Sentences LeetCode Solution in Python 3
class Solution:
def mostWordsFound(self, ss: List[str]) -> int:
return max(s.count(" ") for s in ss) + 1
Maximum Number of Words Found in Sentences LeetCode Solution in C++
int mostWordsFound(vector<string>& s) {
return 1 + accumulate(begin(s), end(s), 0, [](int res, const auto &s) {
return max(res, (int)count(begin(s), end(s), ' ')); });
}
Maximum Number of Words Found in Sentences LeetCode Solution in Java
public int mostWordsFound(String[] sentences) {
return 1 + Stream.of(sentences).mapToInt(s -> (int)s.chars.filter(ch -> ch == ' ').count()).max().getAsInt();
}
Maximum Number of Words Found in Sentences LeetCode Solution in Python
def mostWordsFound(self, sentences: List[str]) -> int:
return max(len(word.split()) for word in sentences)
Maximum Number of Words Found in Sentences LeetCode Solution in JavaScript
/**
* @param {string[]} sentences
* @return {number}
*/
var mostWordsFound = function(sentences) {
let max = 0;
let temp = 0;
for (let i = 0; i < sentences.length; i++) {
temp = sentences[i].split(" ").length;
if (temp > max) {
max = temp;
}
}
return max;
};
Maximum Number of Words Found in Sentences LeetCode Solution in Ruby
def most_words_found(sentences)
sentences.map {|sen| sen.count(' ') + 1}.max
end
Problem 2 – Find All Possible Recipes from Given Supplies LeetCode Solution
You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.
You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.
Example 1:
Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
Example 2:
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
Example 3:
Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".
Constraints:
n == recipes.length == ingredients.length1 <= n <= 1001 <= ingredients[i].length, supplies.length <= 1001 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10recipes[i], ingredients[i][j], andsupplies[k]consist only of lowercase English letters.- All the values of
recipesandsuppliescombined are unique. - Each
ingredients[i]does not contain any duplicate values.
Find All Possible Recipes from Given Supplies LeetCode Solution in C++
vector<string> findAllRecipes(vector<string>& rec, vector<vector<string>>& ing, vector<string>& sup) {
unordered_map<string,vector<string>> graph;
int n = rec.size();
unordered_set<string> s;
for(auto x : sup) s.insert(x); //store all the supplies in unordered set
unordered_map<string,int> indegree; //to store the indegree of all recipes
for(auto x : rec)indegree[x] = 0; //initially take the indegree of all recipes to be 0
for(int i = 0; i < n; i++){
for(int j = 0; j < (int)ing[i].size(); j++){
if(s.find(ing[i][j]) == s.end()){
graph[ing[i][j]].push_back(rec[i]); //if the ingredient required to make a recipe is not in supplies then
indegree[rec[i]]++; //we need to make a directed edge from that ingredient to recipe
}
}
}
//KAHN'S ALGORITHM
queue<string> q;
for(auto x : indegree){
if(x.second == 0){
q.push(x.first);
}
}
vector<string> ans;
while(!q.empty()){
string tmp = q.front();
q.pop();
ans.push_back(tmp);
for(auto nbr : graph[tmp]){
indegree[nbr]--;
if(indegree[nbr] == 0)
q.push(nbr);
}
}
return ans;
}
Find All Possible Recipes from Given Supplies LeetCode Solution in Java
Using BruteForce
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
Set<String> seen = new HashSet<>();
for (String sup : supplies) {
seen.add(sup);
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < recipes.length; ++i) {
q.offer(i);
}
List<String> ans = new ArrayList<>();
int prevSize = seen.size() - 1;
while (seen.size() > prevSize) {
prevSize = seen.size();
mid:
for (int sz = q.size(); sz > 0; --sz) {
int i = q.poll();
for (String ing : ingredients.get(i)) {
if (!seen.contains(ing)) {
q.offer(i);
continue mid;
}
}
seen.add(recipes[i]);
ans.add(recipes[i]);
}
}
return ans;
}
Using Topological sort
public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
List<String> ans = new ArrayList<>();
// Put all supplies into HashSet.
Set<String> available = Stream.of(supplies).collect(Collectors.toCollection(HashSet::new));
Map<String, Set<String>> ingredientToRecipes = new HashMap<>();
Map<String, Integer> inDegree = new HashMap<>();
for (int i = 0; i < recipes.length; ++i) {
int nonAvailable = 0;
for (String ing : ingredients.get(i)) {
if (!available.contains(ing)) {
ingredientToRecipes.computeIfAbsent(ing, s -> new HashSet<>()).add(recipes[i]);
++nonAvailable;
}
}
if (nonAvailable == 0) {
ans.add(recipes[i]);
}else {
inDegree.put(recipes[i], nonAvailable);
}
}
// Toplogical Sort.
for (int i = 0; i < ans.size(); ++i) {
String recipe = ans.get(i);
if (ingredientToRecipes.containsKey(recipe)) {
for (String rcp : ingredientToRecipes.remove(recipe)) {
if (inDegree.merge(rcp, -1, Integer::sum) == 0) {
ans.add(rcp);
}
}
}
}
return ans;
}
Find All Possible Recipes from Given Supplies LeetCode Solution in Python 3
Using BruteForce
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
ans = []
seen = set(supplies)
dq = deque([(r, ing) for r, ing in zip(recipes, ingredients)])
# dummy value for prev_size, just to make sure
# the initial value of prev_size < len(seen)
prev_size = len(seen) - 1
# Keep searching if we have any new finding(s).
while len(seen) > prev_size:
prev_size = len(seen)
for _ in range(len(dq)):
r, ing = dq.popleft()
if all(i in seen for i in ing):
ans.append(r)
seen.add(r)
else:
dq.append((r, ing))
return ans
Using Topological sort
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
available = set(supplies)
ans, ingredient_to_recipe, in_degree = [], defaultdict(set), Counter()
for rcp, ingredient in zip(recipes, ingredients):
non_available = 0
for ing in ingredient:
if ing not in available:
non_available += 1
ingredient_to_recipe[ing].add(rcp)
if non_available == 0:
ans.append(rcp)
else:
in_degree[rcp] = non_available
for rcp in ans:
for recipe in ingredient_to_recipe.pop(rcp, set()):
in_degree[recipe] -= 1
if in_degree[recipe] == 0:
ans.append(recipe)
return ans
Find All Possible Recipes from Given Supplies LeetCode Solution in Python
class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
supplies=set(supplies)
graph=defaultdict(list)
n=len(recipes)
in_degree=defaultdict(int)
for i in range(n):
u=recipes[i]
for v in ingredients[i]:
graph[v].append(u)
in_degree[u]+=1
q=deque([i for i in supplies])
while q:
curr_supp=q.popleft()
for nei in graph[curr_supp]:
in_degree[nei]-=1
if in_degree[nei]==0: q.append(nei)
ans=[]
for recipe in recipes:
if in_degree[recipe]<=0: ans.append(recipe)
return ans
Find All Possible Recipes from Given Supplies LeetCode Solution in
Using BruteForce
var findAllRecipes = function(recipes, ingredients, supplies) {
const setOfIngredients = new Set();
for(const ingredient of supplies) setOfIngredients.add(ingredient);
const result = [];
let track = true;
while(track) {
track = false;
for(let i = 0; i < recipes.length; i++) {
let recipe = recipes[i];
let ingred = ingredients[i];
if(result.indexOf(recipe) >= 0) continue;
let hasAllIngredients = true;
for(const ing of ingred) {
if(!setOfIngredients.has(ing)) {
hasAllIngredients = false;
break;
}
}
if(hasAllIngredients) {
setOfIngredients.add(recipe);
result.push(recipe);
track = true;
}
}
}
return result;
};
Using Topological sort
var findAllRecipes = function(recipes, ingredients, supplies) {
const listOfSupplies = new Set(supplies);
const indexes = new Map();
const map = new Map();
for(let i = 0; i < recipes.length; i++) {
indexes.set(recipes[i], i);
}
const indegree = new Array(recipes.length).fill(0);
for(let i = 0; i < recipes.length; i++) {
let ingr = ingredients[i];
for(let ing of ingr) {
if(listOfSupplies.has(ing)) continue;
if(!map.has(ing)) map.set(ing, []);
map.get(ing).push(recipes[i]);
indegree[i]++;
}
}
const queue = [];
const result = [];
for(let i = 0; i < indegree.length; i++) {
if(indegree[i] === 0) queue.push(i);
}
while(queue.length > 0) {
let idx = queue.shift();
result.push(recipes[idx]);
if(!map.has(recipes[idx])) continue;
const listOfDeps = map.get(recipes[idx]);
removeDeps(listOfDeps, queue, indexes, indegree)
}
return result;
};
function removeDeps(listOfDeps, queue, indexes, indegree) {
for(const dep of listOfDeps) {
let depsIdx = indexes.get(dep)
indegree[depsIdx]--;
if(indegree[depsIdx] === 0) queue.push(depsIdx)
}
}
Problem 3 – Check if a Parentheses String Can Be Valid LeetCode Solution
A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
- It is
(). - It can be written as
AB(Aconcatenated withB), whereAandBare valid parentheses strings. - It can be written as
(A), whereAis a valid parentheses string.
You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,
- If
locked[i]is'1', you cannot changes[i]. - But if
locked[i]is'0', you can changes[i]to either'('or')'.
Return true if you can make s a valid parentheses string. Otherwise, return false.
Example 1:
Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
Example 2:
Input: s = "()()", locked = "0000"
Output: true
Explanation: We do not need to make any changes because s is already valid.
Example 3:
Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0].
Changing s[0] to either '(' or ')' will not make s valid.
Constraints:
n == s.length == locked.length1 <= n <= 105s[i]is either'('or')'.locked[i]is either'0'or'1'.
Check if a Parentheses String Can Be Valid LeetCode Solution in Python 3
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
def validate(s: str, locked: str, op: str) -> bool:
bal, wild = 0, 0
for i in range(len(s)):
if locked[i] == "1":
bal += 1 if s[i] == op else -1
else:
wild += 1
if wild + bal < 0:
return False
return bal <= wild
return len(s) % 2 == 0 and validate(s, locked, '(') and validate(s[::-1], locked[::-1], ')')
Check if a Parentheses String Can Be Valid LeetCode Solution in Java
boolean validate(String s, String locked, char op) {
int bal = 0, wild = 0, sz = s.length();
int start = op == '(' ? 0 : sz - 1, dir = op == '(' ? 1 : - 1;
for (int i = start; i >= 0 && i < sz && wild + bal >= 0; i += dir)
if (locked.charAt(i) == '1')
bal += s.charAt(i) == op ? 1 : -1;
else
++wild;
return Math.abs(bal) <= wild;
}
public boolean canBeValid(String s, String locked) {
return s.length() % 2 == 0 && validate(s, locked, '(') && validate(s, locked, ')');
}
Check if a Parentheses String Can Be Valid LeetCode Solution in C++
bool canBeValid(string s, string locked) {
auto validate = [&](char op) {
int bal = 0, wild = 0, sz = s.size();
int start = op == '(' ? 0 : sz - 1, dir = op == '(' ? 1 : - 1;
for (int i = start; i >= 0 && i < sz && wild + bal >= 0; i += dir)
if (locked[i] == '1')
bal += s[i] == op ? 1 : -1;
else
++wild;
return abs(bal) <= wild;
};
return s.size() % 2 == 0 && validate('(') && validate(')');
}
Check if a Parentheses String Can Be Valid LeetCode Solution in Python
class Solution(object):
def canBeValid(self, s, locked):
if len(s) % 2: # Intuitively, odd-length s cannot be valid.
return False
# traverse each parenthesis forward, treat all unlocked Parentheses as'(' and check if there is ')'
# that cannot be eliminated by previous '(', if it exists, then the input s can't be valid.
balance = 0
for i in range(len(s)):
balance += 1 if s[i] == '(' or locked[i] == '0' else -1
if balance < 0:
return False
# traverse each parenthesis backward, treat all unlocked Parentheses as')' and check if there is '('
# that cannot be eliminated by previous ')', if it exists, then the input s can't be valid.
balance = 0
for i in range(len(s) - 1, -1, -1):
balance += 1 if s[i] == ')' or locked[i] == '0' else -1
if balance < 0:
return False
return True
Problem 4 – Abbreviating the Product of a Range LeetCode Solution
You are given two positive integers left and right with left <= right. Calculate the product of all integers in the inclusive range [left, right].
Since the product may be very large, you will abbreviate it following these steps:
- Count all trailing zeros in the product and remove them. Let us denote this count as
C.- For example, there are
3trailing zeros in1000, and there are0trailing zeros in546.
- For example, there are
- Denote the remaining number of digits in the product as
d. Ifd > 10, then express the product as<pre>...<suf>where<pre>denotes the first5digits of the product, and<suf>denotes the last5digits of the product after removing all trailing zeros. Ifd <= 10, we keep it unchanged.- For example, we express
1234567654321as12345...54321, but1234567is represented as1234567.
- For example, we express
- Finally, represent the product as a string
"<pre>...<suf>eC".- For example,
12345678987600000will be represented as"12345...89876e5".
- For example,
Return a string denoting the abbreviated product of all integers in the inclusive range [left, right].
Example 1:
Input: left = 1, right = 4
Output: "24e0"
Explanation: The product is 1 × 2 × 3 × 4 = 24.
There are no trailing zeros, so 24 remains the same. The abbreviation will end with "e0".
Since the number of digits is 2, which is less than 10, we do not have to abbreviate it further.
Thus, the final representation is "24e0".
Example 2:
Input: left = 2, right = 11
Output: "399168e2"
Explanation: The product is 39916800.
There are 2 trailing zeros, which we remove to get 399168. The abbreviation will end with "e2".
The number of digits after removing the trailing zeros is 6, so we do not abbreviate it further.
Hence, the abbreviated product is "399168e2".
Example 3:
Input: left = 371, right = 375
Output: "7219856259e3"
Explanation: The product is 7219856259000.
Constraints:
1 <= left <= right <= 104
Abbreviating the Product of a Range LeetCode Solution in Python
class Solution(object):
def abbreviateProduct(self, left, right):
prod, suf, zeros, org_digits = 1.0, 1, 0, 0
for n in range(left, right + 1):
prod *= n
while prod >= 1: # keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5
prod /= 10
org_digits += 1 # add 1 while remove 1 digit
suf *= n
while suf % 10 == 0: # count and remove the trailing zeros
zeros += 1
suf //= 10
if suf > 10 ** 14:
suf %= 10 ** 14
if org_digits - zeros <= 10:
return str(int(prod * (10 ** (org_digits - zeros)) + 0.5)) + 'e' + str(zeros)
else:
# you may find that I add 0.5 before cast to int above, but not here.
# It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual
# value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.
# However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not
# error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?
return str(int(prod * 100000)) + '...' + ('0000' + str(suf))[-5:] + 'e' + str(zeros)
Abbreviating the Product of a Range LeetCode Solution in C++
class Solution {
public:
string abbreviateProduct(int left, int right) {
long long suf = 1;
int zeros = 0, org_digits = 0;
double prod = 1.0;
for (int n = left; n <= right; n ++) {
prod *= n;
while (prod >= 1.0) { // keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5
prod /= 10.0;
org_digits ++; // add 1 while remove 1 digit
}
suf *= n;
while (suf % 10 == 0) { // count and remove the trailing zeros
zeros ++;
suf /= 10;
}
if (suf > pow(10, 14)) suf %= (long long)pow(10, 14);
}
if (org_digits - zeros <= 10) {
return to_string((long long)(prod * pow(10, org_digits - zeros) + 0.5)) + 'e' + to_string(zeros);
} else {
// you may find that I add 0.5 before cast to int above, but not here.
// It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual
// value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.
// However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not
// error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?
string str_suf = "0000" + to_string(suf);
return to_string((int)(prod * 100000)) + "..." + str_suf.substr(str_suf.length() - 5) + 'e' + to_string(zeros);
}
}
};
Abbreviating the Product of a Range LeetCode Solution in Java
class Solution {
public String abbreviateProduct(int left, int right) {
long suf = 1;
int zeros = 0, org_digits = 0;
double prod = 1.0;
for (int n = left; n <= right; n ++) {
prod *= n;
while (prod >= 1.0) { // keep 0.1 <= prod < 1.0, so len(str(int(prod * 100000))) == 5
prod /= 10.0;
org_digits ++; // add 1 while remove 1 digit
}
suf *= n;
while (suf % 10 == 0) { // count and remove the trailing zeros
zeros ++;
suf /= 10;
}
if (suf > Math.pow(10, 14)) suf %= (long)Math.pow(10, 14);
}
if (org_digits - zeros <= 10) {
return (long)(prod * Math.pow(10, org_digits - zeros) + 0.5) + "e" + zeros;
} else {
// you may find that I add 0.5 before cast to int above, but not here.
// It is because when org_digits - zeros <= 10, int(prod * (10 ** (org_digits - zeros)) + 0.5) is the actual
// value, we add 0.5 to the last non-zero digits for rounding, 0.5 just means 0.5 over there.
// However here int(prod * 100000) is the first 5-digit prefix, the 6-th digit is also a valid digit not
// error.If we add 0.5 to 6-th digit, how do we calculate the first 6-digit or 7-digit prefix?
String str_suf = "0000" + Long.toString(suf);
return (int)(prod * 100000) + "..." + str_suf.substring(str_suf.length() - 5) + 'e' + zeros;
}
}
}
Abbreviating the Product of a Range LeetCode Solution in Python 3
class Solution:
def abbreviateProduct(self, left: int, right: int) -> str:
ans = prefix = suffix = 1
trailing = 0
flag = False
for x in range(left, right+1):
if not flag:
ans *= x
while ans % 10 == 0: ans //= 10
if ans >= 1e10: flag = True
prefix *= x
suffix *= x
while prefix >= 1e12: prefix //= 10
while suffix % 10 == 0:
trailing += 1
suffix //= 10
if suffix >= 1e10: suffix %= 10_000_000_000
while prefix >= 100000: prefix //= 10
suffix %= 100000
if flag: return f"{prefix}...{suffix:>05}e{trailing}"
return f"{ans}e{trailing}"
Biweekly Contest 68 LeetCode Solution Review:
In our experience, we suggest you solve this Biweekly Contest 68 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Biweekly Contest 68 LeetCode Solution
Conclusion:
I hope this Biweekly Contest 68 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
