def kSimilarity(self, A, B):
    '\n        :type A: str\n        :type B: str\n        :rtype: int\n        '

    def neighbors(s):
        for (i, c) in enumerate(s):
            if (c != B[i]):
                break
        t = list(s)
        for j in xrange((i + 1), len(s)):
            if (t[j] == B[i]):
                (t[i], t[j]) = (t[j], t[i])
                (yield ''.join(t))
                (t[j], t[i]) = (t[i], t[j])
    q = collections.deque([A])
    steps = {A: 0}
    while q:
        s = q.popleft()
        if (s == B):
            return steps[s]
        for t in neighbors(s):
            if (t not in steps):
                steps[t] = (steps[s] + 1)
                q.append(t)
:type A: str
:type B: str
:rtype: int
def kSimilarity(self, A, B):
    '\n        :type A: str\n        :type B: str\n        :rtype: int\n        '

    def neighbors(s):
        for (i, c) in enumerate(s):
            if (c != B[i]):
                break
        t = list(s)
        for j in xrange((i + 1), len(s)):
            if (t[j] == B[i]):
                (t[i], t[j]) = (t[j], t[i])
                (yield .join(t))
                (t[j], t[i]) = (t[i], t[j])
    q = collections.deque([A])
    steps = {A: 0}
    while q:
        s = q.popleft()
        if (s == B):
            return steps[s]
        for t in neighbors(s):
            if (t not in steps):
                steps[t] = (steps[s] + 1)
                q.append(t)