Clean JAVA Code (2 way BFS)


#1

Here, we are running two way BFS, first from starting (A string) and then from target String, i.e. B.
their regenerated are stored in first and end respectively and we then choose the smaller one and do the same regeneration.
Q: Why we are doing in this way?
A: If we start exploring from one side, then the depth and branches will be huge and we may get Out Of Memory Error.
The following code is inspired form LEETCODE DISCUSSION and tried to express in more commented way.

public class Solution {    
HashSet<String> dict; //to convert dict arraylist into hashset, ```contains``` cost is O(1)
public int solve(String A, String B, ArrayList<String> C) {
    dict = new HashSet<>();
    if(A.length()!=B.length())return 0; 
    if(A.equals(B))return 0;
    for(String s:C)
        dict.add(s);
    if(!dict.contains(A) || !dict.contains(B))return 0; //impossible case
    int len = 1;
    //set first contains processing from first side, i.e from string A and end from B
    HashSet<String> first = new HashSet<>(), end = new HashSet<>(),vis = new HashSet<>();
    
    first.add(A);
    end.add(B);
    vis.add(A);
    vis.add(B);
    //mark both of them visited
    
    while(first.size()!=0 && end.size()!=0){

        //cur to obtain all the possible cases form start or end

        HashSet<String> cur = new HashSet<>(); 
        
        if(first.size()>end.size()){
            HashSet<String> s = first;
            first = end;
            end = s;
        }
        for(String k:first){    //for all the strings in smaller* set, we'll try all possible chars for each index
            char[] arr = k.toCharArray();
            for(int i = 0; i<k.length(); i++){
                char old = arr[i];
                for(char c = 'a'; c<='z'; c++){
                    arr[i] = c;
                    String temp = String.valueOf(arr);
                    if(end.contains(temp)){   //if we've processed from end, then return len + 1
                        return len + 1;
                    }
                    if(!vis.contains(temp) && dict.contains(temp))
                    {
                        cur.add(temp);
                        vis.add(temp);
                    }
                }
                arr[i] = old;
            }
        }
        len++;
        first = cur; //since we've visited all the strings of first and their further generated strings are
                         // stored in cur, so we update first to cur. and after exploring, the smaller one is 
                         //chosen to reduce the complexity. 
    }
    return 0;
    
}

}