KK's blog

def alienOrder(self, words: List[str]) -> str:
	# graph = collections.defaultdict(list)
	graph = Counter({c: [] for word in words for c in word})
	for i in range(1, len(words)):
		if not self.populate_one_order(words[i - 1], words[i], graph):
			return ''
	in_degree = collections.defaultdict(int)
	for c in graph.keys():
		in_degree[c] = 0
	for key, li in graph.items():
		for j in range(len(li)):
			in_degree[li[j]] += 1
	res = ''
	queue = deque([node for node, in_degree_num in in_degree.items() if in_degree_num == 0])
	while queue:
		node = queue.popleft()
		res += node
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	return res if len(graph) == len(res) else ''

def populate_one_order(self, word, word2, graph):
	for j in range(min(len(word), len(word2))):
		if word[j] != word2[j]:
			graph[word[j]].append(word2[j])
			return True
	return False if len(word) > len(word2) else True

def firstBadVersion(self, n):
	start, end = 0, n
	while start + 1 < end:
		mid = start + (end - start) // 2
		if isBadVersion(mid):
			end = mid
		else:
			start = mid
	if isBadVersion(start):
		return start
	if isBadVersion(end):
		return end
	return -1   

def wordPatternMatch(self, pattern: str, s: str) -> bool:
	if not pattern or not s:
		return False
	return self.dfs(pattern, s, 0, 0, {}, set())

def dfs(self, pattern, s, start_p, start_s, pattern_to_s, s_set):
	if start_p >= len(pattern) and start_s >= len(s):
		return True
	if start_p >= len(pattern) or start_s >= len(s):
		return False
	char = pattern[start_p]
	if char in pattern_to_s:
		word = pattern_to_s[char]
		if not s[start_s:].startswith(word):
			return False
		return self.dfs(pattern, s, start_p + 1, start_s + len(word), pattern_to_s, s_set)
		
	for j in range(start_s, len(s)):
		matched_word = s[start_s:j + 1]
		'''if char in pattern_to_s and pattern_to_s[char] != matched_word:
			continue
		if char not in pattern_to_s and matched_word in s_set:  # remembers
			continue'''
		if matched_word in s_set:
			continue
		pattern_to_s[char] = matched_word
		s_set.add(matched_word)
		if self.dfs(pattern, s, start_p + 1, j + 1, pattern_to_s, s_set):
			return True
		s_set.remove(matched_word)
		pattern_to_s.pop(char)
	return False

class RandomizedSet(TestCases):

    def __init__(self):
        self.nums = []
        self.key_to_index = {}

    def insert(self, val: int) -> bool:
        if val in self.key_to_index:
            return False
        self.nums.append(val)
        self.key_to_index[val] = len(self.nums) - 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.key_to_index:
            return False
        index = self.key_to_index[val]
        last_val = self.nums[len(self.nums) - 1]
        self.nums[index] = last_val
        self.key_to_index[last_val] = index
        self.key_to_index.pop(val)  # remember to put it last
        self.nums.pop()
        return True

    def getRandom(self) -> int:
        return self.nums[random.randint(0, len(self.nums) - 1)]

def checkValidString(self, s: str) -> bool:
	stack_left, stack_star = [], []
	for i in range(len(s)):
		if s[i] == '(':
			stack_left.append(i)
		if s[i] == '*':
			stack_star.append(i)
		if s[i] == ')':
			if stack_left:  # match ( first rather than * because * can be empty
				stack_left.pop()
			elif stack_star:
				stack_star.pop()
			else:
				return False
	while stack_left and stack_star:  # use * to match (
		if stack_left[-1] > stack_star[-1]:  # consider *(
			return False
		stack_left.pop()
		stack_star.pop()
	return len(stack_left) == 0  # stack_star can be non empty      

def checkValidString(self, s: str) -> bool:
	lo = hi = 0
	for char in s:
		if char == '(':
			lo += 1
			hi += 1
		if char == '*':
			if lo > 0:  # treat * as empty space
				lo -= 1
			hi += 1
		if char == ')':
			if lo > 0:  # treat the previous * as empty space
				lo -= 1
			hi -= 1
		if hi < 0:  # the num of right parenthesis > left ones
			return False
	return lo == 0  # the num of right parenthesis should equal to left ones