Is the judge time too strict? My code got a TLE


  • 0
    Z

    Is the judge time too strict? Why my code always got TLE?
    It's a dfs and mems all the shortest path, and got a TLE.

        public static int ladderLength(String start, String end, HashSet<String> dict) {
        resPath.clear();
        visit.clear();
        visit.put(start, 0);
        dict.add(start);
        dict.add(end);
        solve(start, end, dict, new LinkedList<String>());
        return resPath.size();
    }
    
    static void solve(String str, String target, HashSet<String> dict, LinkedList<String> path) {
    	path.addLast(str);
    	if (str.equals(target)) {
    		if (resPath.size() == 0 || resPath.size() > path.size()) {
    			resPath = new LinkedList<String>(path);
    		}
    		path.removeLast();
    		return;
    	}
    	StringBuilder sb = new StringBuilder(str);
    	for (int i = 0; i < str.length(); i++) {
    		char backup = sb.charAt(i);
    		for (int j = 0; j < 26; j++) {
    			char c = (char)('a' + j);
    			if (c == backup) continue;
    			sb.setCharAt(i, c);
    			String checkString = sb.toString();
    			if (dict.contains(checkString)) {
    				if (visit.get(checkString) == null || visit.get(checkString) > path.size()) {
    					visit.put(checkString, path.size());
    					solve(checkString, target, dict, path);
    				}
    			}
    		}
    		sb.setCharAt(i, backup);
    	}
    	path.removeLast();
    }
    static LinkedList<String> resPath = new LinkedList<String>();
    static HashMap<String, Integer> visit = new HashMap<String, Integer>();

  • 1
    S

    Your dfs is so brute force. You can do some optimization in it, like if you have reached some words in dict by x step, you do not have to go deeper recursion next time, when you reach that word again by y step, if x < y.

    However, I prefer BFS to solve the problem, since DFS may causes stack overflow.


Log in to reply
 

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