K-Similar Strings LeetCode solution in JavaScript

1
var kSimilarity = function (s1, s2) {
2
  // abc --> bca
3
  // swap from 0: a !== b, find next b, swap(0,1) --> bac
4
  // swap from 1: a !== c, find next c, swap(1,2) --> bca
5
  return bfs(s1, s2);
6
};
7

8
const bfs = (a, b) => {
9
  if (a === b) return 0;
10
  const visited = new Set();
11
  const queue = [];
12
  queue.push([a, 0, 0]); // str, idx, swapCount
13
  while (queue.length > 0) {
14
    let [s, idx, cnt] = queue.shift();
15
    while (s[idx] === b[idx]) {
16
      idx++;
17
    }
18
    for (let j = idx + 1; j < s.length; j++) {
19
      if (s[j] === b[idx]) {
20
        s = swap(s, idx, j);
21

22
        if (s === b) {
23
          return cnt + 1;
24
        }
25

26
        if (!visited.has(s)) {
27
          queue.push([s.slice(), idx, cnt + 1]);
28
          visited.add(s.slice());
29
        }
30

31
        // swap back for later index
32
        s = swap(s, idx, j);
33
      }
34
    }
35
  }
36
  return -1;
37
};
38

39
const swap = (s, i, j) => {
40
  let arr = s.split("");
41
  let tmp = arr[i];
42
  arr[i] = arr[j];
43
  arr[j] = tmp;
44
  return arr.join("");
45
};