LeetCode Solutions

			

class Solution {
 public:
  int kSimilarity(string s1, string s2) {
    int ans = 0;
    queue<string> q{{s1}};
    unordered_set<string> seen{{s1}};

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

    return -1;
  }

 private:
  vector<string> getChildren(string& curr, const string& target) {
    vector<string> children;
    int i = 0;  // 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;
  }
};

			

class Solution {
  public int kSimilarity(String s1, String s2) {
    int ans = 0;
    Queue<String> q = new ArrayDeque<>(Arrays.asList(s1));
    Set<String> seen = new HashSet<>(Arrays.asList(s1));

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

    return -1;
  }

  private List<String> getChildren(final String curr, final String target) {
    List<String> children = new ArrayList<>();
    char[] charArray = curr.toCharArray();
    int i = 0; // 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;
  }
}

			

class Solution:
  def kSimilarity(self, s1: str, s2: str) -> int:
    ans = 0
    q = deque([s1])
    seen = {s1}

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

    return -1

  def _getChildren(self, curr: str, target: str) -> List[str]:
    children = []
    s = list(curr)
    i = 0  # 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