Here is my solution using Bi-directional bfs. 1-direction solution got timed out so I changed it to 2-ended solution. For practice, another similar problem that uses Bi-directional bfs is https://leetcode.com/problems/word-ladder-ii/. Following is my solution:

```
def openLock(self, deadends, target):
visited = set(deadends)
s1 = set(["0000"])
s2 = set([target])
if "0000" in deadends:
return -1
cnt = 0
while s1 and s2:
s_tmp = set()
while s1:
pattern = s1.pop()
if pattern in s2:
return cnt
visited.add(pattern)
for i in range(4):
for offset in [1, -1]:
newpattern = pattern[:i] + str((int(pattern[i])+offset)%10) + pattern[i+1:]
if newpattern not in visited:
s_tmp.add(newpattern)
s1 = s_tmp
s1, s2 = s2, s1
cnt += 1
return -1
```