Description#
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.lengths1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.s2 is an anagram of s1.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
def next(s):
i = 0
while s[i] == s2[i]:
i += 1
res = []
for j in range(i + 1, n):
if s[j] == s2[i] and s[j] != s2[j]:
res.append(s2[: i + 1] + s[i + 1 : j] + s[i] + s[j + 1 :])
return res
q = deque([s1])
vis = {s1}
ans, n = 0, len(s1)
while 1:
for _ in range(len(q)):
s = q.popleft()
if s == s2:
return ans
for nxt in next(s):
if nxt not in vis:
vis.add(nxt)
q.append(nxt)
ans += 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public int kSimilarity(String s1, String s2) {
Deque<String> q = new ArrayDeque<>();
Set<String> vis = new HashSet<>();
q.offer(s1);
vis.add(s1);
int ans = 0;
while (true) {
for (int i = q.size(); i > 0; --i) {
String s = q.pollFirst();
if (s.equals(s2)) {
return ans;
}
for (String nxt : next(s, s2)) {
if (!vis.contains(nxt)) {
vis.add(nxt);
q.offer(nxt);
}
}
}
++ans;
}
}
private List<String> next(String s, String s2) {
int i = 0, n = s.length();
char[] cs = s.toCharArray();
for (; cs[i] == s2.charAt(i); ++i) {
}
List<String> res = new ArrayList<>();
for (int j = i + 1; j < n; ++j) {
if (cs[j] == s2.charAt(i) && cs[j] != s2.charAt(j)) {
swap(cs, i, j);
res.add(new String(cs));
swap(cs, i, j);
}
}
return res;
}
private void swap(char[] cs, int i, int j) {
char t = cs[i];
cs[i] = cs[j];
cs[j] = t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
int kSimilarity(string s1, string s2) {
queue<string> q{{s1}};
unordered_set<string> vis{{s1}};
int ans = 0;
while (1) {
for (int i = q.size(); i; --i) {
auto s = q.front();
q.pop();
if (s == s2) {
return ans;
}
for (auto& nxt : next(s, s2)) {
if (!vis.count(nxt)) {
vis.insert(nxt);
q.push(nxt);
}
}
}
++ans;
}
}
vector<string> next(string& s, string& s2) {
int i = 0, n = s.size();
for (; s[i] == s2[i]; ++i) {}
vector<string> res;
for (int j = i + 1; j < n; ++j) {
if (s[j] == s2[i] && s[j] != s2[j]) {
swap(s[i], s[j]);
res.push_back(s);
swap(s[i], s[j]);
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| func kSimilarity(s1 string, s2 string) int {
next := func(s string) []string {
i := 0
res := []string{}
for ; s[i] == s2[i]; i++ {
}
for j := i + 1; j < len(s1); j++ {
if s[j] == s2[i] && s[j] != s2[j] {
res = append(res, s[:i]+string(s[j])+s[i+1:j]+string(s[i])+s[j+1:])
}
}
return res
}
q := []string{s1}
vis := map[string]bool{s1: true}
ans := 0
for {
for i := len(q); i > 0; i-- {
s := q[0]
q = q[1:]
if s == s2 {
return ans
}
for _, nxt := range next(s) {
if !vis[nxt] {
vis[nxt] = true
q = append(q, nxt)
}
}
}
ans++
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
def f(s):
cnt = sum(c != s2[i] for i, c in enumerate(s))
return (cnt + 1) >> 1
def next(s):
i = 0
while s[i] == s2[i]:
i += 1
res = []
for j in range(i + 1, n):
if s[j] == s2[i] and s[j] != s2[j]:
res.append(s2[: i + 1] + s[i + 1 : j] + s[i] + s[j + 1 :])
return res
q = [(f(s1), s1)]
dist = {s1: 0}
n = len(s1)
while 1:
_, s = heappop(q)
if s == s2:
return dist[s]
for nxt in next(s):
if nxt not in dist or dist[nxt] > dist[s] + 1:
dist[nxt] = dist[s] + 1
heappush(q, (dist[nxt] + f(nxt), nxt))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
public int kSimilarity(String s1, String s2) {
PriorityQueue<Pair<Integer, String>> q
= new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
q.offer(new Pair<>(f(s1, s2), s1));
Map<String, Integer> dist = new HashMap<>();
dist.put(s1, 0);
while (true) {
String s = q.poll().getValue();
if (s.equals(s2)) {
return dist.get(s);
}
for (String nxt : next(s, s2)) {
if (!dist.containsKey(nxt) || dist.get(nxt) > dist.get(s) + 1) {
dist.put(nxt, dist.get(s) + 1);
q.offer(new Pair<>(dist.get(nxt) + f(nxt, s2), nxt));
}
}
}
}
private int f(String s, String s2) {
int cnt = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != s2.charAt(i)) {
++cnt;
}
}
return (cnt + 1) >> 1;
}
private List<String> next(String s, String s2) {
int i = 0, n = s.length();
char[] cs = s.toCharArray();
for (; cs[i] == s2.charAt(i); ++i) {
}
List<String> res = new ArrayList<>();
for (int j = i + 1; j < n; ++j) {
if (cs[j] == s2.charAt(i) && cs[j] != s2.charAt(j)) {
swap(cs, i, j);
res.add(new String(cs));
swap(cs, i, j);
}
}
return res;
}
private void swap(char[] cs, int i, int j) {
char t = cs[i];
cs[i] = cs[j];
cs[j] = t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| using pis = pair<int, string>;
class Solution {
public:
int kSimilarity(string s1, string s2) {
priority_queue<pis, vector<pis>, greater<pis>> q;
q.push({f(s1, s2), s1});
unordered_map<string, int> dist;
dist[s1] = 0;
while (1) {
auto [_, s] = q.top();
q.pop();
if (s == s2) {
return dist[s];
}
for (auto& nxt : next(s, s2)) {
if (!dist.count(nxt) || dist[nxt] > dist[s] + 1) {
dist[nxt] = dist[s] + 1;
q.push({dist[nxt] + f(nxt, s2), nxt});
}
}
}
}
int f(string& s, string& s2) {
int cnt = 0;
for (int i = 0; i < s.size(); ++i) {
cnt += s[i] != s2[i];
}
return (cnt + 1) >> 1;
}
vector<string> next(string& s, string& s2) {
int i = 0, n = s.size();
for (; s[i] == s2[i]; ++i) {}
vector<string> res;
for (int j = i + 1; j < n; ++j) {
if (s[j] == s2[i] && s[j] != s2[j]) {
swap(s[i], s[j]);
res.push_back(s);
swap(s[i], s[j]);
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| func kSimilarity(s1 string, s2 string) int {
next := func(s string) []string {
i := 0
res := []string{}
for ; s[i] == s2[i]; i++ {
}
for j := i + 1; j < len(s1); j++ {
if s[j] == s2[i] && s[j] != s2[j] {
res = append(res, s[:i]+string(s[j])+s[i+1:j]+string(s[i])+s[j+1:])
}
}
return res
}
f := func(s string) int {
cnt := 0
for i := range s {
if s[i] != s2[i] {
cnt++
}
}
return (cnt + 1) >> 1
}
q := hp{pair{f(s1), s1}}
dist := map[string]int{s1: 0}
for {
s := heap.Pop(&q).(pair).s
if s == s2 {
return dist[s]
}
for _, nxt := range next(s) {
if v, ok := dist[nxt]; !ok || v > dist[s]+1 {
dist[nxt] = dist[s] + 1
heap.Push(&q, pair{dist[nxt] + f(nxt), nxt})
}
}
}
}
type pair struct {
v int
s string
}
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
a, b := h[i], h[j]
return a.v < b.v
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
|
