Is there anyone who solved the problem with Java? I used BFS method, but always TLE. Need help


  • 0
    M
    import java.util.*;
    
    
    public class Solution {
    	public int _pathLength;
    	public int _level;
    	
    	public Solution() {
    		_pathLength = 9999999;
    		_level = 999999;
    	}
    	
    	
    	
    
    	public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
    		
    		ArrayList<ArrayList<String>> solution = new ArrayList<ArrayList<String>>();		
    		HashSet<String> dictUsed = new HashSet<String>();
    		
    		findSolutionBFS2(start,end,dict,dictUsed,solution);
    			
    		return solution;
            
        }
    	
    	
    	//if we can pass from word s1 to word s1, then the function returns true, otherwise returns false;
    	
    	public boolean checkConnection(String s1, String s2) {
    		
    		Set<Character> set1 = new HashSet<Character>();
    		Set<Character> set2 = new HashSet<Character>();
    		
    		
    		for (int i = 0; i < s1.length(); i++) {
    			set1.add(s1.charAt(i));
    			set2.add(s2.charAt(i));
    		}
    		
    		set1.retainAll(set2);
    
    		return (set1.size() == (set2.size()-1));
    	}
    	
    	
    
    
    	
    	public void findSolutionBFS2(String start, String end, HashSet<String> dict, HashSet<String> dictUsed, ArrayList<ArrayList<String>> solution) {
    		
    		// use ArrayList and a pointer to simulate a queue
    
    		ArrayList<Node> pathQ = new ArrayList<Node>();
    		int pointer = 0;
    
    		// add the first elements into the queue
    		Node first = new Node(start,-1,0);
    		pathQ.add(first);
    		
    		while (pointer < pathQ.size()) {
    			
    			// if we have already found a path, then quit the while loop
    			if (pathQ.get(pointer)._level > _level) { break;}
    
    			// if the actual path can connect to the target word,
    			// we will reconstruct the whole solution path
    			if (checkConnection(end,pathQ.get(pointer)._string)) {
    										
    				LinkedList<String> arr = new LinkedList<String>();
    				
    				Node tNode = pathQ.get(pointer);
    				arr.add(end);
    				_level = pathQ.get(pointer)._level;
    				
    				while (tNode._last > -1 ) {
    					arr.addFirst(tNode._string);
    					tNode = pathQ.get(tNode._last);
    				}
    				
    				arr.addFirst(tNode._string);
    			
    				
    				solution.add(new ArrayList<String>(arr));
    				pointer++;
    				continue;
    		
    			}
    		
    			// search for the next level
    			for (String ss : dict) {
    				if ( checkConnection(ss, pathQ.get(pointer)._string) && !dictUsed.contains(ss) ) {
    					Node newNode = new Node(ss,pointer,pathQ.get(pointer)._level+1);
    					pathQ.add(newNode);
    					dictUsed.add(ss);
    				}
    			}	
    			pointer++;
    			}
    			
    	}
    	
    	
    }
    
    class Node {
    	
    	public String _string;			// _string is the word
    	public int  _last;			// register the previous element in the solution path, _last is the index of the pathQ
    	public int _level;			// the level in the BFS algorithm
    	
    	public Node(String s, int n, int m) {
    		_string = s;
    		_last = n;
    		_level = m;
    		
    	}
    	
    }

Log in to reply
 

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