K-Similar Strings LeetCode solution in Java

1
class Solution {
2
  public int kSimilarity(String s1, String s2) {
3
    HashSet<String> vis = new HashSet<>();
4

5
    ArrayDeque<String> queue = new ArrayDeque<>();
6
    int level = 0;
7
    queue.add(s1);
8

9
    while (queue.size() > 0) {
10
      int size = queue.size();
11
      for (int i = 0; i < size; i++) {
12

13
        String rem = queue.remove(); // remove
14

15
        if (vis.contains(rem)) { // Mark*
16
          continue;
17
        }
18
        vis.add(rem);
19

20
        if (rem.equals(s2)) { // Work
21
          return level;
22
        }
23

24
        // Add
25
        for (String s : getNeighbors(rem, s2)) {
26
          if (!vis.contains(s)) {
27
            queue.add(s);
28
          }
29
        }
30
      }
31
      level++;
32
    }
33
    return -1;
34
  }
35

36
  public ArrayList<String> getNeighbors(String rem, String s2) {
37
    ArrayList<String> res = new ArrayList<>();
38

39
    int idx = -1;
40
    for (int i = 0; i < rem.length(); i++) {
41
      if (rem.charAt(i) != s2.charAt(i)) {
42
        idx = i;
43
        break;
44
      }
45
    }
46

47
    for (int j = idx + 1; j < rem.length(); j++) {
48
      if (rem.charAt(j) == s2.charAt(idx)) {
49
        String s = swap(rem, idx, j);
50
        res.add(s);
51
      }
52
    }
53

54
    return res;
55
  }
56

57
  public String swap(String str, int i, int j) {
58
    StringBuilder sb = new StringBuilder(str);
59
    char chi = sb.charAt(i);
60
    char chj = sb.charAt(j);
61

62
    sb.setCharAt(i, chj);
63
    sb.setCharAt(j, chi);
64

65
    return sb.toString();
66
  }
67
}