Keep hitting a Time Limit Exceeded exception - BFS - Word Ladder - JAVA


  • 2
    Q

    I implement the BFS using a queue. It always hit the TLE exception. Please help pointing out my mistake.
    (Last executed input: "sand", "acne", ["slit","bunk",....)
    Thanks so much.

    Code:

    public int ladderLength(String start, String end, HashSet<String> dict) {
    	//building a graph
    	dict.add(start);
    	dict.add(end);
    
    	int n = dict.size();
    
    	//the graph consisting nodes array
    	Node[] nodes= new Node[n];
    
    	Iterator itr = dict.iterator();
    
    	Node startNode=null, endNode=null;
    
    	//create node for each dict word
    	for (int i = 0; i < n; i++) {
    		Node nd = new Node();
    		nd.data = (String)itr.next();
    		nodes[i] = nd;
    		//set start and end
    		if(nd.data.equals(start))
    			startNode = nd;
    
    		if(nd.data.equals(end))
    			endNode = nd;
    	}
    
    	//O(n-square)
    	//find neighbors of each node
    	for (int i = 0; i < n; i++) {
    		Node current = nodes[i];
    		current.neighbor = neighbor(current,nodes);
    	}
    
    	//BFS implemented by a Queue
    	Queue<Node> aQ = new LinkedList<Node>();
    
    	aQ.add(startNode);
    
    	int counter = 1;
    	while(!aQ.isEmpty()){ //O(n-square) n is the # of edge
    		Node pointer = (Node)aQ.poll();
    		mark(pointer);
    		if(pointer==endNode){
    			return pointer.distance;
    		}
    
    		Iterator<Node> neiItr = pointer.neighbor.iterator();
    		while (neiItr.hasNext()) {
    			Node current = (Node)neiItr.next();
    			if(current.visited==false){
    				aQ.add(current);
    				current.distance = ++counter;
    			}			
    		}
    	}
    	return 0;
    }
    
    public void mark(Node t){
    	t.visited=true;
    }
    
    public void markAll(ArrayList<Node> t){
    	Iterator itr = t.iterator();
    	while(itr.hasNext()){
    		((Node)itr.next()).visited=true;
    	}
    }
    
    
    public ArrayList<Node> neighbor(Node nd, Node[] nodes){
    	ArrayList<Node> neighors = new ArrayList<Node>();
    
    	for (int i = 0; i < nodes.length; i++) {
    		Node current = nodes[i];
    		if(current.isNeighborOf(nd))
    			neighors.add(current);
    	}
    
    	return neighors;
    }
    
    
    class Node{
    	String data;
    	int distance = 0;
    	boolean visited = false;
    	ArrayList<Node> neighbor;
    
    	/**
    	 * O(n)
    	 * @param t
    	 * @return
    	 */
    	public boolean isNeighborOf(Node t){
    		int ctr = 0;
    		for (int i = 0; i < data.length(); i++) {
    			if(data.charAt(i)!=t.data.charAt(i)){
    				ctr++;
    				if(ctr>1)
    					return false;
    			}
    		}
    
    		//ctr has to be bigger than 1
    		//set is non duplicate
    		return true;
    	}
    }

  • 11
    S

    Seems you use O(N^2) to build the graph, then find to shortest path from start string to end string. It is a solution, but not efficient.

    You can do the BFS in this way, initialize the BFS queue with only one element start string. Then go thru the BFS queue one by one, as we know the queue will increase during the BFS process. The way to expand the current string to see if it can generate another string in the dictionary and not appear in the BFS queue before. How to generate? Scan the characters in the string one by one, try to replace with other characters a to z.

    If you do BFS in the way above, you do not have to touch all words in the dictionary to build graph. Considering the dictionary might be huge, it will be more elegant than your solution.


  • 0
    Q

    Thanks for answering! I will try what you suggested.


  • 0
    K

    Thank you. That was a neat trick. I


  • 0
    1

    The complexity of your approach is O(n*len(word)). If the length of the words ~ n then the complexity degenerates to O(n^2) again. I tried to build a graph the naive way but I got a TLE. Seems like the length of the words is always small compared to n in the test cases.


  • 0
    D

    I had the same concern when I thought about this idea, however, len(word) should only be about O(log n) solely because by nature, our languages are as efficient as possible in terms of Kolmogorov complexity. What I mean is that there would be exponentially many words at a given short length, and number of words of extraordinary length is very small, in which case O(n^2) is just competitive. Even then, one can expect more number of words than the length of the word itself, not exponentially many but definitely at least linear. I believe that sublinear, which would mean n = o(len(word)), is extremely unlikely. So this approach definitely rules.


  • 0
    F

    current.distance = ++counter;

    This step is wrong


Log in to reply
 

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