https://leetcode.com/articles/k-similar-strings/
Strings
A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in Aexactly K times so that the resulting string equals B.
Given two anagrams
A and B, return the smallest K for which A and B are K-similar.
Example 1:
Input: A = "ab", B = "ba" Output: 1
Example 2:
Input: A = "abc", B = "bca" Output: 2
Example 3:
Input: A = "abac", B = "baca" Output: 2
Example 4:
Input: A = "aabc", B = "abca" Output: 2
Note:
1 <= A.length == B.length <= 20AandBcontain only lowercase letters from the set{'a', 'b', 'c', 'd', 'e', 'f'}
https://leetcode.com/problems/k-similar-strings/discuss/140099/JAVA-BFS-32-ms-cleanconciseexplanationwhatever
The trick is that you just need to swap the first (a,b)->(b,a) pair every round, instead of other pairs like (c,d)->(d,c) (otherwise it would cause TLE), and BFS would guarantee the shortest path.
update sorry I just realized that my explaination has some flaw (the code is correct though).
I turned
into
and it can't pass all test case, which means we are not actually swapping the direct reversed pair, we are just trying to fix the some wrong character in each loop.
To make it better understood, I suggest we change this line to:
which means we only swap the i-th and j-th character when j-th character is wrong and it happends to be the target character of i-th position.
So that in each round we will repair the first unordered character and as a result move forward at least 1 step.
I turned
if (s.charAt(j)==B.charAt(j) || s.charAt(i)!=B.charAt(j) ) continue;into
if (s.charAt(j)==B.charAt(j) || s.charAt(i)!=B.charAt(j) || s.charAt(j)!=B.charAt(i) ) continue;and it can't pass all test case, which means we are not actually swapping the direct reversed pair, we are just trying to fix the some wrong character in each loop.
To make it better understood, I suggest we change this line to:
if (s.charAt(j)==B.charAt(j) || s.charAt(j)!=B.charAt(i) ) continue;which means we only swap the i-th and j-th character when j-th character is wrong and it happends to be the target character of i-th position.
So that in each round we will repair the first unordered character and as a result move forward at least 1 step.
public int kSimilarity(String A, String B) {
if (A.equals(B)) return 0;
Set<String> vis= new HashSet<>();
Queue<String> q= new LinkedList<>();
q.add(A);
vis.add(A);
int res=0;
while(!q.isEmpty()){
res++;
for (int sz=q.size(); sz>0; sz--){
String s= q.poll();
int i=0;
while (s.charAt(i)==B.charAt(i)) i++;
for (int j=i+1; j<s.length(); j++){
if (s.charAt(j)==B.charAt(j) || s.charAt(i)!=B.charAt(j) ) continue;
String temp= swap(s, i, j);
if (temp.equals(B)) return res;
if (vis.add(temp)) q.add(temp);
}
}
}
return res;
}
public String swap(String s, int i, int j){
char[] ca=s.toCharArray();
char temp=ca[i];
ca[i]=ca[j];
ca[j]=temp;
return new String(ca);
}
Simple and straightforward. Swap the characters in
Use a
A using backtracking to get close to B.Use a
map to memorize.class Solution {
public int kSimilarity(String A, String B) {
Map<String, Integer> map = new HashMap<>();
return backtrack(A.toCharArray(), B, map, 0);
}
private int backtrack(char[] A, String B, Map<String, Integer> map, int i) {
String sa = new String(A);
if (sa.equals(B)) {
return 0;
}
if (map.containsKey(sa)) {
return map.get(sa);
}
int min = Integer.MAX_VALUE;
while (i < A.length && A[i] == B.charAt(i)) {
i++;
}
for (int j = i + 1; j < B.length(); j++) {
if (A[j] == B.charAt(i)) {
swap(A, i, j);
int next = backtrack(A, B, map, i + 1);
if (next != Integer.MAX_VALUE) {
min = Math.min(min, next + 1);
}
swap(A, i, j);
}
}
map.put(sa, min);
return min;
}
private void swap(char[] cs, int i, int j) {
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
}
Update:
Basically, this problem seems like a cyclic swapping problem. I get some hints from this post.
The intuition behind this is, in order to get the minimum swaps, we need to divide the string into groups as many as possible. Then for each group with the size of
Consider
Look into each group, it's a cyclic swapping, which means for each swap, we put a char into the right place. In this situation, we can use the strategy in my post to simply get the first right char at A[i].
Basically, what the backtracking do is simulate all the possible swapping, trying to find the minimum swaps
The intuition behind this is, in order to get the minimum swaps, we need to divide the string into groups as many as possible. Then for each group with the size of
k, we need k - 1 swaps, for example:Consider
A = "abcde", B = "bcaed", we can divide the A into abc and de, the total swaps is 2 + 1 = 3.Look into each group, it's a cyclic swapping, which means for each swap, we put a char into the right place. In this situation, we can use the strategy in my post to simply get the first right char at A[i].
Basically, what the backtracking do is simulate all the possible swapping, trying to find the minimum swaps
https://leetcode.com/problems/k-similar-strings/discuss/151500/Logical-Thinking-with-Clear-Java-Code
n fact, the essence of the problem is to get the minimum number of swaps A needs to make itself equal to B.
It is a shortest-path problem so we can utilize BFS. The
graph we build sets all possible strings that can be swapped from A as nodes, and an edge exists if one string can be transformed into the other by one swap. We start at A, and target at B.
However, that will cause TLE. We set all possible strings that can be formed by swapping the positions of two letters in A' one time as neighbours of A', however, only those can make A and B differ less are meaningful neighbours. That is, if A'[i] != B[i] but A'[j] == B[i], the string formed by swap(A, i, j) is a meaningful neighbour of A'. Please note that we just need to swap the first pair (A'[i], A'[j]) we meet for the order of swap doesn't matter.
public int kSimilarity(String A, String B) {
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(A);
visited.add(A);
int level = 0;
while (!queue.isEmpty()) {
int sz = queue.size();
for (int i = 0; i < sz; i++) {
String curNode = queue.poll();
if (curNode.equals(B)) {
return level;
}
for (String neighbour : getNeighbours(curNode, B)) {
if (!visited.contains(neighbour)) {
queue.offer(neighbour);
visited.add(neighbour);
}
}
}
level++;
}
return -1;
}
private List<String> getNeighbours(String S, String B) {
List<String> result = new ArrayList<>();
char[] arr = S.toCharArray();
int i = 0;
for (; i < arr.length; i++) {
if (arr[i] != B.charAt(i)) {
break;
}
}
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] == B.charAt(i)) {
swap(arr, i, j);
result.add(new String(arr));
swap(arr, i, j);
}
}
return result;
}
private void swap(char[] arr, int i, int j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}https://www.cnblogs.com/sfzyk/p/9577186.html
给定两个字符串， 判断最少经过多少次swap 可以使得 两个字符串一致，
首先类似的问题 是存在一个 underlying graph 的。
每一个字母都对应着一个节点，两个字符串的不一致表示为图上的一条有向边
每一个字母都对应着一个节点，两个字符串的不一致表示为图上的一条有向边
最后的问题转化为 图上的最（多）圆环分解
要注意的是贪心策略并不能解决问题（即每一次都选择 最小的那个圆环构成原图）
使用记忆化搜索策略。
将一个所有可能存在路径存在与否的向量作为相应的状态
https://www.twblogs.net/a/5bafa9022b7177781a0f3bf3/zh-cn
由题可知，我们需要求解从初始状态（
A或B，这里设为A）转换到目标状态（B）所需的最小步骤数K，即求从图的一个顶点到另一顶点的最短路径长度。因为图是未知的，所以这里采用BFS的策略求解。首先最简单的想法就是从起点A出发，BFS遍历所有可到达的顶点（状态），这样做虽然可行，但显然复杂度太高，需要进一步优化。在最简单的BFS中，很显然有些交换字符的步骤是多余的，而为了达到目的，交换字符后A字符串的相应位置至少要有一个字符与B的相应位置处的字符相同，即 A[j] == B[i] 的时候我们可以交换 A[i] 和 A[j] 使得 A[i] == B[i] ，当然，最理想的情况是当 A[i] == B[j] && A[j] == B[i] 时交换，这样交换后A、B 中 i、j两处位置的字符就都一致了。另外，若 A[j] == B[j] ，则不应再交换 A[j] 处的字符。
通过上面的条件，我们排除了一些不必要的路径。若能找到最理想的条件我们就可以直接“走”这条路径，而在交换后只有一个字符能相符的情况下我们就需要对所有情况进行检查了。实际上，我们只需按顺序依次遍历
A 的每一个位置，按上述条件进行对比，只要有一处符合交换条件，我们就可以接受该情况，再从该情况出发进行BFS，这样就能很大程度上减少计算次数。而因为我们依序遍历（以i作为迭代下标），并且在只有一个字符能够符合的情况下我们需要检查所有符合条件的交换位置（所有符合 A[j] == B[i] 的 j ），所以即使在其它位置存在最理想的交换情况我们也不会错过。