Algorithm
Problem Name: 854. K-Similar Strings
Problem Link: https://leetcode.com/problems/k-similar-strings/
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 Explanation: The two string are 1-similar because we can use one swap to change s1 to s2: "ab" --> "ba".
Example 2:
Input: s1 = "abc", s2 = "bca" Output: 2 Explanation: The two strings are 2-similar because we can use two swaps to change s1 to s2: "abc" --> "bac" --> "bca".
Constraints:
1 <= s1.length <= 20s2.length == s1.lengths1ands2contain only lowercase letters from the set{'a', 'b', 'c', 'd', 'e', 'f'}.s2is an anagram ofs1.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const kSimilarity = function(A, B) {
if (A === B) return 0
let arr = [[B, 0]]
while (arr.length > 0) {
let len = arr.length
for (let i = 0; i < len; i++) {
let [cur, step] = arr.shift()
for (let i = 0; i < cur.length; i++) {
if (cur[i] === A[i]) continue
for (let j = i + 1; j < cur.length; j++) {
if (cur[j] !== A[i]) continue
let newStr =
cur.substring(0, i) +
cur[j] +
cur.substring(i + 1, j) +
cur[i] +
cur.substring(j + 1)
if (newStr === A) return step + 1
if (cur[i] === A[j]) arr.unshift([newStr, step + 1])
else arr.push([newStr, step + 1])
}
break
}
}
}
}
Input
s1 = "ab", s2 = "ba"
Output
1
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def kSimilarity(self, A, B):
b, n, k, stack = [c for c in B], len(A), float("inf"), [(0, 0, [c for c in A])]
while stack:
i, cnt, s = stack.pop()
while i < n and s[i] == b[i]:
i += 1
if i == n:
if cnt < k:
k = cnt
else:
for j in range(i + 1, n):
if s[j] == b[i] and s[j] != b[j]:
ls = s[:]
ls[i], ls[j] = ls[j], ls[i]
stack.append((i + 1, cnt + 1, ls))
return k
Input
s1 = "ab", s2 = "ba"
Output
1