Java Bidirectional Search Solution (faster than BFS)


  • 0
    S

    Each valid gene string can be considered as a node of a graph, and when two strings has exactly one different char, there is an edge connecting these two vertices.

    Then, this problem is converted to a graph problem: given two vertices (start and end), find the shortest path from one to the other.

    We know BFS is faster than DFS for such a scenario.

    Here I introduce something theoretically faster than BFS, called Bidirectional Search.

    From Cracking the Coding Interview, 6th Edition, Page 108:

    "Bidirectional search is used to find the shortest path between a source and destination node. It operates by essentially running two simultaneous breadth-first searches, one from each node. When their searches collide, we have found a path. Too see why this is faster, consider a graph where every node has at most k adjacent nodes and the shortest path from node s to node t has length d.

    "In traditional breadth-first search, we would search up to k nodes in the first "level" of the search. In the second level, we would search up to k nodes for each of those first k nodes, so k^2 nodes total (thus far). We would do this d times, so that's O(k^d) nodes.

    "In bidirectional search, we have two searches that collide after approximately d/2 levels ( the midpoint of the path). The search from s visits approximately k^(d/2), as does the search from t. That's approximately 2k^(d/2), or O(k^(d/2)), nodes total."

    Below is a Java implementation:

    public int minMutation(String start, String end, String[] bank) {
        List<Integer>[] graph = new List[bank.length];
        for (int i = 0; i < bank.length; i++) {
            graph[i] = new ArrayList<>();
            for (int j = 0; j < bank.length; j++)
                if (canMutate(bank[i], bank[j])) graph[i].add(j);
        }
    	
        int targetIdx = -1;
        for (int i = 0; i < bank.length; i++) {
            if (bank[i].equals(end)) {targetIdx = i; break;}
        }
        if (targetIdx == -1) return -1;
    	
        // endXXX means something calculated from end to start
        int[] endDist = new int[bank.length];
        Arrays.fill(endDist, -1);
        endDist[targetIdx] = 0;
        Queue<Integer> endQ = new ArrayDeque<>();
        for (int idx : graph[targetIdx]) {
            endQ.add(idx);
            endDist[idx] = 1;
        }
    	
        // startXXX means something calculated from start to end
        int[] startDist = new int[bank.length];
        Arrays.fill(startDist, -1);
        Queue<Integer> startQ = new ArrayDeque<>();
        for (int i = 0; i < bank.length; i++) {
            if (canMutate(start, bank[i])) {
                if (bank[i].equals(end)) return 1;
                startQ.add(i);
                startDist[i] = 1;
            }
        }
    	
        while (!startQ.isEmpty() && !endQ.isEmpty()) {
            int startIdx = startQ.poll();
            for (int nextIdx : graph[startIdx]) {
                if (startDist[nextIdx] != -1) continue;
                else if (endDist[nextIdx] >= 0) return startDist[startIdx] + endDist[nextIdx] + 1;
                else {
                    startDist[nextIdx] = startDist[startIdx] + 1;
                    startQ.add(nextIdx);
    	    }
            }
    		
            int endIdx = endQ.poll();
            for (int nextIdx : graph[endIdx]) {
                if (endDist[nextIdx] != -1) continue;
                else if (startDist[nextIdx] > 0) return startDist[nextIdx] + endDist[endIdx] + 1;
                else {
                    endDist[nextIdx] = endDist[endIdx] + 1;
                    endQ.add(nextIdx);
                }
            }
        }
    	
        return -1;
    }
    
    private boolean canMutate(String gen1, String gen2) {
        int diff = 0;
        for (int i = 0; i < gen1.length(); i++)
            diff += gen1.charAt(i) == gen2.charAt(i) ? 0 : 1;
        return diff == 1;
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.