433.md

434. Number of Segments in a String

Solution 1

# BFS
class Solution(object):
    def minMutation(self, start, end, bank):
        """
        :type start: str
        :type end: str
        :type bank: List[str]
        :rtype: int
        """
        if start == end:
            return 0
        bank = set(bank)
        if start in bank:
            bank.remove(start)
        if end not in bank:
            return -1
        q = deque([(start, 0)])
        while q:
            cur_info, cur_step = q.popleft()
            for i in range(len(cur_info)):
                for c in "ACGT":
                    if cur_info[i] == c:
                        continue
                    new_info = cur_info[:i] + c + cur_info[i + 1:]
                    if new_info in bank:
                        if new_info == end:
                            return cur_step + 1
                        q.append((new_info, cur_step + 1))
                        bank.remove(new_info)
        return -1