KK's blog

def changeNodes(self, existingTree, newTree) -> int:
	if not existingTree and not newTree:
		return 0
	if not existingTree or not newTree:
		return self.count(existingTree) + self.count(newTree)
	res = 0 if existingTree.key == newTree.key and existingTree.val == newTree.val else 1
	existing_children_dict = self.get_children_dict(existingTree.children)
	new_tree_children_dict = self.get_children_dict(newTree.children)
	for key in existing_children_dict.keys() & new_tree_children_dict.keys(): # in both
		res += self.changeNodes(existing_children_dict[key], new_tree_children_dict[key])
	for key in existing_children_dict.keys() - new_tree_children_dict.keys(): # in existing tree not in new tree
		res += self.count(existing_children_dict[key])
	for key in new_tree_children_dict.keys() - existing_children_dict.keys():  # in new tree not in existing tree
		res += self.count(new_tree_children_dict[key])
	return res

def count(self, root):
	if not root:
		return 0
	res = 0
	for child in root.children:
		res += self.count(child)
	return 1 + res

def get_children_dict(self, children):
	key_to_node = {}
	for child in children:
		key_to_node[child.key] = child
	return key_to_node

class FileSystem(TestCases):

    def __init__(self):
        self.head = TrieNode('')

    def createPath(self, path: str, value: int) -> bool:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                if i == len(segments) - 1: # match all the previous segments
                    it.children[segment] = TrieNode(segment)
                else:
                    return False
            it = it.children[segment]
        if it.value != -1: # exists
            return False
        it.value = value
        return True

    def get(self, path: str) -> int:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                return -1
            it = it.children[segment]
        return it.value

class TrieNode:

    def __init__(self, name):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.name = name
        self.value = -1

class FileSystem2(TestCases):

    def __init__(self):
        self.path_to_val = defaultdict()

    def createPath(self, path: str, value: int) -> bool:

        if path == "/" or len(path) == 0 or path in self.path_to_val:
            return False

        # search from the right
        parent = path[:path.rfind('/')]
        if len(parent) > 1 and parent not in self.path_to_val:
            return False

        self.path_to_val[path] = value
        return True

    def get(self, path: str) -> int:
        return self.path_to_val.get(path, -1)

def numSimilarGroups(self, strs: List[str]) -> int:
	if not strs:
		return 0
	visited, groups, word_set = set(), 0, set(strs)
	for s in strs:
		if s in visited:
			continue
		self.bfs(word_set, s, visited)
		groups += 1
	return groups

def bfs(self, word_set, start, visited):
	queue = collections.deque([start])
	visited.add(start)
	while queue:
		node = queue.popleft()
		for s in word_set:
			if s in visited:
				continue
			if node == s or not self.buddyStrings(node, s):
				continue
			queue.append(s)
			visited.add(s)

def buddyStrings(self, s: str, goal: str) -> bool:
	if len(s) != len(goal):
		return False
	if s == goal and len(set(s)) < len(goal):  # any dups
		return True
	diff = [(a, b) for a, b in zip(s, goal) if a != b]
	return True if len(diff) == 2 and diff[0] == diff[1][::-1] else False