Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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 <= 100
1 <= sentences[i].length <= 100
sentences[i]
consists only of lowercase English letters and ' '
only.sentences[i]
does not have leading or trailing spaces.sentences[i]
are separated by a single space.class Solution:
def mostWordsFound(self, ss: List[str]) -> int:
return max(s.count(" ") for s in ss) + 1
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), ' ')); });
}
public int mostWordsFound(String[] sentences) {
return 1 + Stream.of(sentences).mapToInt(s -> (int)s.chars.filter(ch -> ch == ' ').count()).max().getAsInt();
}
def mostWordsFound(self, sentences: List[str]) -> int:
return max(len(word.split()) for word in sentences)
/**
* @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;
};
def most_words_found(sentences)
sentences.map {|sen| sen.count(' ') + 1}.max
end
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.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j]
, and supplies[k]
consist only of lowercase English letters.recipes
and supplies
combined are unique.ingredients[i]
does not contain any duplicate values.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;
}
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;
}
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
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
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)
}
}
A parentheses string is a non-empty string consisting only of '('
and ')'
. It is valid if any of the following conditions is true:
()
.AB
(A
concatenated with B
), where A
and B
are valid parentheses strings.(A)
, where A
is 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
,
locked[i]
is '1'
, you cannot change s[i]
.locked[i]
is '0'
, you can change s[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.length
1 <= n <= 105
s[i]
is either '('
or ')'
.locked[i]
is either '0'
or '1'
.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], ')')
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, ')');
}
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(')');
}
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
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:
C
.3
trailing zeros in 1000
, and there are 0
trailing zeros in 546
.d
. If d > 10
, then express the product as <pre>...<suf>
where <pre>
denotes the first 5
digits of the product, and <suf>
denotes the last 5
digits of the product after removing all trailing zeros. If d <= 10
, we keep it unchanged.1234567654321
as 12345...54321
, but 1234567
is represented as 1234567
."<pre>...<suf>eC"
.12345678987600000
will be represented as "12345...89876e5"
.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
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)
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);
}
}
};
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;
}
}
}
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}"
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
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 >>