Skip to content

854. K-Similar Strings 👍

  • Time: $O(n^2k)$
  • Space: $O(n^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
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  int kSimilarity(string s1, string s2) {
    queue<string> q{{s1}};
    unordered_set<string> seen{{s1}};

    for (int step = 0; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        string curr = q.front();
        q.pop();
        if (curr == s2)
          return step;
        for (const string& child : getChildren(curr, s2)) {
          if (seen.contains(child))
            continue;
          q.push(child);
          seen.insert(child);
        }
      }

    return -1;
  }

 private:
  vector<string> getChildren(string& curr, const string& target) {
    vector<string> children;
    int i = 0;  // the first index s.t. curr[i] != target[i]
    while (curr[i] == target[i])
      ++i;

    for (int j = i + 1; j < curr.length(); ++j)
      if (curr[j] == target[i]) {
        swap(curr[i], curr[j]);
        children.push_back(curr);
        swap(curr[i], curr[j]);
      }

    return children;
  }
};

 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
class Solution {
  public int kSimilarity(String s1, String s2) {
    Queue<String> q = new ArrayDeque<>(List.of(s1));
    Set<String> seen = new HashSet<>(Arrays.asList(s1));

    for (int step = 0; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final String curr = q.poll();
        if (curr.equals(s2))
          return step;
        for (final String child : getChildren(curr, s2)) {
          if (seen.contains(child))
            continue;
          q.offer(child);
          seen.add(child);
        }
      }

    return -1;
  }

  private List<String> getChildren(final String curr, final String target) {
    List<String> children = new ArrayList<>();
    char[] charArray = curr.toCharArray();
    int i = 0; // the first index s.t. curr.charAt(i) != target.charAt(i)
    while (curr.charAt(i) == target.charAt(i))
      ++i;

    for (int j = i + 1; j < charArray.length; ++j)
      if (curr.charAt(j) == target.charAt(i)) {
        swap(charArray, i, j);
        children.add(String.valueOf(charArray));
        swap(charArray, i, j);
      }

    return children;
  }

  private void swap(char[] charArray, int i, int j) {
    final char temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
  }
}

 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
class Solution:
  def kSimilarity(self, s1: str, s2: str) -> int:
    q = collections.deque([s1])
    seen = {s1}

    step = 0
    while q:
      for _ in range(len(q)):
        curr = q.popleft()
        if curr == s2:
          return step
        for child in self._getChildren(curr, s2):
          if child in seen:
            continue
          q.append(child)
          seen.add(child)
      step += 1

    return -1

  def _getChildren(self, curr: str, target: str) -> list[str]:
    children = []
    s = list(curr)
    i = 0  # the first index s.t. curr[i] != target[i]
    while curr[i] == target[i]:
      i += 1

    for j in range(i + 1, len(s)):
      if s[j] == target[i]:
        s[i], s[j] = s[j], s[i]
        children.append(''.join(s))
        s[i], s[j] = s[j], s[i]

    return children