Accepted Java solution based on Dijkstra's algorithm


  • 4
    P

    I use a Dijkstra's algorithm for solving problem. Each node (vertex) is a word with neigbours of one letter difference. Distance between neigbour nodes is 1. Please see comments.

    public int ladderLength(String start, String end, Set<String> dict) {
    	
    	// Init vertices
    	WordVertex startVertex = new WordVertex(start);
    	WordVertex endVertex = new WordVertex(end);
    	startVertex.dist = 0;
    	List<WordVertex> vertices = new ArrayList<WordVertex>();
    	vertices.add(startVertex);
    	vertices.add(endVertex);
    	for (String word:dict) {
    		vertices.add(new WordVertex(word));
    	}
    	
    	// Construct graph
    	for(int i=0; i<vertices.size(); i++) {
    		WordVertex vertex = vertices.get(i);
    		for(int j=i+1; j<vertices.size(); j++) {
    			WordVertex neighbor = vertices.get(j);
    			int diff = 0;
    			for (int k=0; k<vertex.word.length(); k++) {
    				if (vertex.word.charAt(k) != neighbor.word.charAt(k) && diff++ == 1) {
    					break;
    				}
    			}
    			if (diff == 1) {
    				vertex.neighbors.add(neighbor);
    				neighbor.neighbors.add(vertex);
    			}
    			
    		}
    	}
    	
    	// Find shortest path. Dijkstra's algorithm.
    	PriorityQueue<WordVertex> queue = new PriorityQueue<WordVertex>();
    	for (WordVertex v:vertices) {
    		queue.add(v);
    	}
    	while(!queue.isEmpty()) {
    		WordVertex v = queue.poll();
    		if (v.dist == Integer.MAX_VALUE) continue;
    		for (WordVertex n:v.neighbors) {
    			if (!n.visited) {
    				if (v.dist + 1 < n.dist) {
    					n.dist = v.dist + 1;
    					queue.remove(n);
    					queue.add(n);
    				}
    			}
    		}
    		v.visited = true;
    	}
    	
    	return endVertex.dist == Integer.MAX_VALUE ? 0 : endVertex.dist + 1;
    }

  • 0
    S

    Do you think a edge-weight==1 Dijkstra is the same as BFS?


  • 3
    Y

    why you like to use Dijkstra in an unweighted graph?


  • 0
    F

    Weight is 1, and I used Dijkstra too.


  • 0
    S

    if weight is 1, you can just use breadth first search.


Log in to reply
 

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