Test "cet", "ism" test takes forever to run.


  • 0
    J

    On the "cet", "ism" test case, I am running it forever. I am using a BFS approach. I have outlined the algorithm in comments

    // check if there is such a word to get from the dict to the end
    	Boolean wordExists = false;
    	for (String s : dict) {
    		Integer difference = 0;
    		for (int idx = 0; idx < end.length(); idx ++) {
    			if (s.charAt(idx) != end.charAt(idx)) {
    				difference ++;
    			}
    		}
    		if (difference == 1) {
    			// there is such a word
    			//System.out.println(s);
    			wordExists = true;
    			break;
    		}
    	}
    	
    	if (!wordExists) {
    		return new ArrayList<ArrayList<String>>();
    	}
    	
    	ArrayList<ArrayList<String>> toReturn = new ArrayList<ArrayList<String>>();
    	Queue<ArrayList<String>> ladders = new LinkedList<ArrayList<String>>();
    	Queue<HashSet<String>> dicts = new LinkedList<HashSet<String>>();
    	ArrayList<String> aLadder = new ArrayList<String>();
    	aLadder.add(start);
    	ladders.add(aLadder);
    	dicts.add(dict);
    	Boolean reachedDestination = false;
    	Integer shortestDistance = -1;
    	while (!ladders.isEmpty()) {
    		/*
    		 * For each popped ladder, get the last string and see if it is
    		 * 1 distance away from the end.
    		 * If it is, then we have reached our destination. Find all the ladders where the last string is 1 away
    		 * from the end.
    		 * If it isn't, then check if there exists a
    		 * word in the dictionary that is 1 away from it.
    		 * If there is such a word, then spawn a new ladder and insert
    		 * it to ladders queue. Remove the word from the corresponding dictionary, make a new dictionary and add that to the dictionaries queue.
    		 */
    		ArrayList<String> currLadder = ladders.remove();
    		HashSet<String> currDict = dicts.remove();
    		String lastString = currLadder.get(currLadder.size()-1);
    		/*
    		 * Check if the lastString is 1 away from the end
    		 */
    		Integer differenceToEnd = 0;
    		for (int idx = 0; idx < end.length(); idx ++) {
    			if (lastString.charAt(idx) != end.charAt(idx)) {
    				differenceToEnd ++;
    			}
    		}
    		if (differenceToEnd == 1) {
    			// Reached the destination
    			if (shortestDistance < 0) {
    				reachedDestination = true;
    				shortestDistance = currLadder.size();
    				currLadder.add(end);
    				toReturn.add(currLadder);
    			} else if (currLadder.size() == shortestDistance) {
    				currLadder.add(end);
    				toReturn.add(currLadder);
    			}
    		} else if (reachedDestination && currLadder.size() > shortestDistance) {
    			// We are done here.
    			return toReturn;
    		} else if (differenceToEnd > 1 && !reachedDestination) {
    			for (int idx = 0; idx < lastString.length(); idx ++) {
    				char[] currentStringCharArray = lastString.toCharArray();
    				for (char c = 'a'; c <= 'z'; c ++) {
    					currentStringCharArray[idx] = c;
    					String newString = new String(currentStringCharArray);
    					/* Calculate difference from newString to end */
    					Integer newDiffToEnd = 0;
    					for (int ind = 0; ind < end.length(); ind ++) {
    						if (newString.charAt(ind) != end.charAt(ind)) {
    							newDiffToEnd ++;
    						}
    					}
    					if (!newString.equals(start) && (newDiffToEnd <= differenceToEnd)) {
    						if (currDict.contains(newString)) {
    							@SuppressWarnings("unchecked")
    							ArrayList<String> newLadder = (ArrayList<String>)currLadder.clone();
    							currDict.remove(newString);
    							newLadder.add(newString);
    							@SuppressWarnings("unchecked")
    							HashSet<String> newDict = (HashSet<String>)currDict.clone();
    							dicts.add(newDict);
    							ladders.add(newLadder);
    							System.out.println("ladder size = " + newLadder.size());
    							System.out.println("queue size = " + ladders.size());
    						}
    					}
    				}
    			}
    		}
    	}
    	return toReturn;
    }
    

    Is there a way to optimize this algorithm?


Log in to reply
 

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