DevExCode

LeetCode 854: K-Similar Strings

StringBreadth-First Search

Problem Description

Explanation

To solve this problem, we can use a breadth-first search (BFS) approach to find the minimum number of swaps required to make the two strings k-similar. We start with the initial string s1 and keep swapping characters in it until we reach the target string s2. At each step, we generate all possible strings that can be obtained by swapping two characters and add them to the queue for further exploration. We continue this process until we find the target string s2.

Algorithm:

  1. Initialize a queue with the initial string s1.
  2. Initialize a set to keep track of visited strings.
  3. Initialize the number of swaps k to 0.
  4. While the queue is not empty:
    • Increment k by 1.
    • Iterate over the strings currently in the queue:
      • Generate all possible strings that can be obtained by swapping two characters in the current string.
      • If a generated string matches the target string s2, return the current k.
      • If the generated string has not been visited before, add it to the queue and mark it as visited.
  5. If the target string is not found, return -1.

Time Complexity: The time complexity of this approach is O(n * n!), where n is the length of the input string.

Space Complexity: The space complexity is O(n!), where n is the length of the input string, due to the number of possible permutations.

View on LeetCode

Solutions

class Solution {
    public int kSimilarity(String s1, String s2) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(s1);
        visited.add(s1);
        int k = 0;

        while (!queue.isEmpty()) {
            k++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                if (current.equals(s2)) {
                    return k - 1;
                }
                List<String> neighbors = getNeighbors(current, s2);
                for (String neighbor : neighbors) {
                    if (!visited.contains(neighbor)) {
                        queue.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
        }

        return -1;
    }

    private List<String> getNeighbors(String s, String target) {
        List<String> neighbors = new ArrayList<>();
        char[] sArr = s.toCharArray();
        int i = 0;
        while (sArr[i] == target.charAt(i)) {
            i++;
        }
        for (int j = i + 1; j < sArr.length; j++) {
            if (sArr[j] == target.charAt(i)) {
                swap(sArr, i, j);
                neighbors.add(new String(sArr));
                swap(sArr, i, j); // backtrack
            }
        }
        return neighbors;
    }

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

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...