Thanks for the clarification. I thought it is invalid if we have two in adjacent.
Posts made by wangruinju
RE: Clarify on "no more than two adjacent fence posts"
RE: Count Binary Substrings
My two pointer solution:
class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ res = 0 for i in range(0, len(s)-1): if s[i] != s[i+1]: res += self.helper(i, s) return res def helper(self, i, s): count = 1 while i-count >= 0 and i+1+count < len(s) and s[i-count] == s[i] and s[i+1+count] == s[i+1]: count += 1 return count
Python solution using BFS
class Solution(object): def minMutation(self, start, end, bank): """ :type start: str :type end: str :type bank: List[str] :rtype: int """ queue = collections.deque() visited = set() queue.append((start, 0)) dict_words = set(bank) while queue: word, steps = queue.popleft() if word == end: return steps if word not in visited: visited.add(word) for i in range(len(word)): for s in ["A", "C", "G", "T"]: if s != word[i]: mutate_word = word[:i] + s + word[i+1:] if mutate_word in dict_words and mutate_word not in visited: queue.append((mutate_word, steps + 1)) return -1