433.md

N-ary Tree Level Order Traversal

Description

link

---

Solution BFS

• traditional BFS, 巧妙之处在于把步数加入到current set当中，每次完全遍历保证一定能覆盖到变化

---

Code

Complexity T : O(n) M :

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        queue = []
        queue.append((start,0))
        bankSet = set(bank)
        
        while queue:
            curr, step = queue.pop(0)
            if curr == end:
                return step
            for i in range(len(curr)):
                for c in "AGCT":
                    mutation = curr[:i] + c + curr[i+1:]
                    if mutation in bankSet:
                        bankSet.remove(mutation)
                        queue.append((mutation,step+1))
                        
        return -1