LeetCode 854 K-Similar Strings

LeetCode

Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

Example 1:

Input: s1 = “ab”, s2 = “ba”
Output: 1

Example 2:

Input: s1 = “abc”, s2 = “bca”
Output: 2

Constraints:

1 <= s1.length <= 20 s2.length == s1.length
s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}. s2 is an anagram of s1.

题目大意：

两字符，交换两个位置，使得他们相等，求最小交换次数

解题思路：

最值考虑用BFS，难点在于生成neighbor，见注意事项

解题步骤：

N/A

注意事项：

1. 用例子写程序node = abc s2 = cba, 先找到第一个不同位i，然后找下一个不同位j，这个不同位node[j]需要与目标s2[i]相同，贪心法
2. 倒数第二行要break，否则TLE，因为只要找到一位可以交换这一层的BFS算是结束

Python代码：

def kSimilarity(self, s1: str, s2: str) -> int:
	queue = collections.deque([s1])
	visited = set([s1])
	distance = {s1: 0}
	while queue:
		node = queue.popleft()
		if node == s2:
			return distance[node]
		for i in range(len(node)): # abc, cba
			if node[i] == s2[i]:
				continue
			for j in range(i + 1, len(node)):
				if node[j] == s2[j]:
					continue
				if node[j] == s2[i]:
					ss = node[:i] + node[j] + node[i + 1:j] + node[i] + node[j + 1:]
					if ss in visited:
						continue
					queue.append(ss)
					visited.add(ss)
					distance[ss] = distance[node] + 1
			break # remember
	return -1

算法分析：

时间复杂度为O(解大小)，空间复杂度O(解大小)