Time Limit Exceed!! don't understand why


  • 0
    E

    I use BFS to find every ladder. A new queue of next level is generated in every recursion. One level becomes the final level until there is a acceptable list of this level.
    I thought this code might get a Memory Limit Exceed because the queue keeps lists, but result is a TLE.
    I don't understand which part leads to the TLE.

    public class Solution {

    private List<List<String>> ladders;
    private String end;
    private int len;
    private Set<String> dict;
    private boolean done;
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    	this.end = end;
    	this.dict = dict;
    	this.len = end.length();
    	ladders = new ArrayList<List<String>> ();
    	List<String> pioneer = new ArrayList<String> ();
    	Map<String, Boolean> passerby = new HashMap<String, Boolean> ();
    	Queue<List<String>> testStep = new LinkedList<List<String>> ();
    	testStep.add(new ArrayList<String>());
    	testStep.peek().add(start);
    	BFS (testStep, passerby);
                return ladders;
        }
    public void BFS (Queue<List<String>> testStep, Map<String, Boolean> passerby) {
    	if (done || testStep.isEmpty()) return;
    	Queue<List<String>> nextStep = new LinkedList<List<String>> ();
    	Map<String, Boolean> newDict = new HashMap<String, Boolean> ();
    	while (!testStep.isEmpty()) {
    		List<String> past = testStep.poll();
    		String start = past.get(past.size() - 1);
    		for (int i = 0;i < len;i ++)
    			for (char alteration = 'a';alteration <= 'z';alteration ++) {
    				if (start.charAt(i) == alteration) continue;
    				StringBuilder possibleNext = new StringBuilder(start);
    				possibleNext.setCharAt(i, alteration);
    				String pn = possibleNext.toString();
    				if (pn.equals(end)) {
    					past.add(pn);
    					ladders.add(new ArrayList<String> (past));
    					past.remove(past.size() - 1);
    					done = true;
    					continue;
    				}
    				if (dict.contains(pn))
    					if (!passerby.containsKey(pn)) {
    						past.add(pn);
    						nextStep.add(new ArrayList<String>(past));
    						past.remove(past.size() - 1);
    						newDict.put(pn, true);
    					}					
    			}
    	}
    	passerby.putAll(newDict);
    	BFS (nextStep, passerby);
    }
    

    }


  • 0
    X

    Keep tracking of all BFS paths cost a lot- especially when the graph is huge, there may exists way too many feasible intermediate paths to check. To avoid this, simply store the intermediate levels(no explicit path), then backtrack from the sink(end), which feels like traverse a tree(treat the sink as root), this process automatically cut useless nodes, start from sink all nodes can reach the source, but not vice versa(think about it)!


Log in to reply
 

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