After 6 weeks of cruel daily check in, I am finally free from solve the daily problem everyday in cruel group. The condition of free is that the contest rank is within top 500 in the world and solving all 4 problems in weekly contest. Congratulations on me.

2047. Number of Valid Words in a Sentence

Sign on problem. It is more difficult than usual. The corner case needs to be careful of. For example, ‘-‘ is not a valid word.

classSolution: defcountValidWords(self, sentence: str) -> int: defisPunctuation(c): return c == '!'or c == '.'or c == ',' defisLower(c): returnord(c) >= ord('a') andord(c) <= ord('z') defcheck(word): # It only contains lowercase letters, hyphens, and/or punctuation (no digits). # There is at most one hyphen '-'. If present, it should be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid). # There is at most one punctuation mark. If present, it should be at the end of the token. hyphenCount = 0 punctuationCount = 0 for c in word: if c == '-': hyphenCount += 1 if c.isdigit(): returnFalse if isPunctuation(c): punctuationCount += 1 if hyphenCount > 1or punctuationCount > 1: returnFalse if punctuationCount == 1andnot isPunctuation(word[-1]): returnFalse if hyphenCount == 1: l = word.split('-') iflen(l) != 2: returnFalse ifnot (len(l[0]) >= 1and isLower(l[0][-1])) ornot (len(l[1]) >= 1and isLower(l[1][0])): returnFalse returnTrue ans = 0 words = sentence.split() for word in words: # print (word) if check(word): # print('Yes') ans += 1 return ans

Time complexity: O(N), Space complexity: O(N).

A easier solution is re, aka regular expression.

1 2 3 4 5 6 7 8 9 10 11

import re

classSolution: defcountValidWords(self, sentence: str) -> int: pattern = re.compile('(^[a-z]+(-[a-z]+)?)?[,.!]?$') word_count = 0 for word in sentence.split(): if pattern.match(word): word_count = word_count + 1 return word_count

Time complexity: O(N), Space complexity: O(N).

2048. Next Greater Numerically Balanced Number

Many people’s solutions are “Accepted” using brute force. Iterate every number greater than n, and check if it is numerically balanced. I proposed a better solution in contest. Because of 0 <= n <= 10^6, I manually enumerate all numerically balanced numbers and find the next greater one. The possible balance numbers is countable. One trick here is using permutations to iterate all permutations of a string.

classSolution: defnextBeautifulNumber(self, n: int) -> int: # 1digit: 1 # 2digit: 22 # 3digit: 333 or 1+2 # 4digit: 1+3 or 4 # 5digit: 5 or 1+4 or 2+3 # 6digit: 6 or 1+5 or 2+4 or 1+2+3 # 7digit: 7 or 1+6 or 1+2+4 1224444 if n == 10**6: return1224444 ans = 1224444 s = str(n) # 6! 720 defcheck(l): ans = float('inf') origin = '' for i in l: origin += str(i) * i perms = [''.join(p) for p in permutations(origin)] for s in perms: i = int(s) if i > n: ans = min(ans, i) return ans ans = min(ans, check([6])) ans = min(ans, check([1, 5])) ans = min(ans, check([2, 4])) ans = min(ans, check([1, 2, 3])) ans = min(ans, check([5])) ans = min(ans, check([1, 4])) ans = min(ans, check([2, 3])) ans = min(ans, check([4])) ans = min(ans, check([1, 3])) ans = min(ans, check([3])) ans = min(ans, check([1, 2])) ans = min(ans, check([2])) ans = min(ans, check([1])) return ans

Time complexity: O(13 * 6!), Space complexity: O(6!).

2049. Count Nodes With the Highest Score

We could use DFS to calculate every subtrees’ size.

Calculate the score of each node. 3 possible states when deleting a node: two children, one child, no child. A corner case is the root node. It do not have the parent.

Find the highest score and its frequency.

A corner case is that the products could overflow int. It is 10^5 * 10^5 maximally. long long could avoid this runtime error easily.