A. Maximum Number of Words Found in Sentences (opens new window)

DETAILS

int mostWordsFound(vector<string>& S) {
        int ans = 0;
        for (auto s : S) {
            int cur = 1;
            for (auto ch : s)
                if (ch == ' ')
                    cur += 1;
            ans = max(ans, cur);
        }                    
        return ans;
    }

B. Find All Possible Recipes from Given Supplies (opens new window)

BFS Topology sort.

DETAILS

def findAllRecipes(self, R: List[str], D: List[List[str]], S: List[str]) -> List[str]:
        P, G, S = collections.defaultdict(list), collections.defaultdict(int), set(S)
        n, ans = len(R), []
        ind = [0] * n
        for i in range(n):
            for j in range(n):
                if R[i] in D[j]:
                    G[j] += 1
                    P[i].append(j)
                    ind[j] += 1
                    
        dq = collections.deque()
        for i in range(n):
            if ind[i] == 0:
                dq.append(i)
        
        while dq:
            cur = dq.popleft()
            okay = True
            for ing in D[cur]:
                if ing not in S:
                    okay = False
                    continue
            if okay:
                S.add(R[cur])
                ans.append(R[cur])
                for p in P[cur]:
                    G[p] -= 1
                    if G[p] == 0:
                        dq.append(p)
        
        return ans

C. Check if a Parentheses String Can Be Valid (opens new window)

DETAILS

def canBeValid(self, S: str, L: str) -> bool:
        n = len(S)
        if n % 2: return False
        
        bal = 0
        for ch, lock in zip(S, L):
            if lock == '0' or ch == '(':
                bal += 1
            elif ch == ')':
                bal -= 1
            if bal < 0:
                return False
        
        bal = 0
        for ch, lock in zip(reversed(S), reversed(L)):
            if lock == '0' or ch == ')':
                bal += 1
            elif ch == '(':
                bal -= 1
            if bal < 0:
                return False
            
        return True

D. Abbreviating the Product of a Range (opens new window)

DETAILS

def abbreviateProduct(self, left, right):
        pref, suff, trailing, val = 1.0, 1, 0, 0
        for n in range(left, right + 1):
            pref *= n
            while pref >= 1:
                pref /= 10
                val += 1
            suff *= n
            while not suff % 10:
                trailing += 1
                suff //= 10
            
            if suff > 1e14:
                suff %= 10 ** 14
        if val - trailing > 10:
            pre = str(pref*100000)[:5]
            tail = str(suff).zfill(5)[-5:]
            return f'{pre}...{tail}e{trailing}'
        pre = int(pref * (0.5 + 10 ** (val - trailing))) 
        return f'{pre}e{trailing}'