Are the test cases biased?


  • 3
    B

    The test cases seems to be biased towards large dict size but short word length. you will get a timeout if you build the "transform tree" BFS by trying all words in the dict. You can only pass if you "generate" all possible next words and see if it's in the dict.

    "generating all possible next word" approach is only better in "large dict", "short word" cases. Try each word in dict is better if the length of word is long. The problem statement didn't say either way is true so either one should be equally good...

    Ok, I understand if you put it in the context of a real language, the size of dict will be large and length of word will be (relatively) short. My point is just that's if you want people to optimize for something, then it should probably be stated in the problem statement.

    For reference, the "build transform tree using bfs by trying all words in the dict" solution that gets timeout is like this:

    class Node {
    	String s;
    	int steps;
    
    	Node(String s, int steps) {
    		this.s = s;
    		this.steps = steps;
    	}
    }
    
    public class Solution {
    	// find the shortest "transform path" by build a "transform" tree starting from "start"
    	// use bfs so we can stop as soon as "end" is reached.
    	public int ladderLength(String start, String end, HashSet<String> dict) {
    		if(dict.contains(start)) dict.remove(start);
    		if(dict.contains(end)) dict.remove(end);
    		
    		ArrayDeque<Node> stack = new ArrayDeque<Node>();
    		stack.add(new Node(start, 1));
    
    		while (!stack.isEmpty()) {
    			Node n = stack.remove();
    			if (canTransform(n.s, end))
    				return n.steps + 1;
    
    			// try every world in dict to see if it can be the next transform step
    			// this will timeout for large dict sizes
    			Iterator<String> itr = dict.iterator();
    			while (itr.hasNext()) {
    				String word = itr.next();
    				if (canTransform(n.s, word)) {
    					itr.remove(); // remove word from dict once it can be reached
    					stack.add(new Node(word, n.steps + 1));
    				}
    			}
    
    			// generate every possible "next word" from n.s and check if it's in the dict
    			// this will pass all test cases
    			/*
    			char[] ca = n.s.toCharArray();
    			for(int i=0; i<ca.length; i++){
    				char oldc = ca[i];
    				for(char c='a'; c<='z'; c++){
    					ca[i] = c;
    					String s = new String(ca);
    					if(dict.contains(s)){
    						dict.remove(s);//remove word from dict once it can be reached
    						stack.add(new Node(s, n.steps+1));
    					}
    				}
    				ca[i] = oldc;
    			}
    			*/
    		}
    
    		return 0;
    	}
    
    	boolean canTransform(String from, String to) {
    		int diff = 0;
    		for (int i = 0; i < from.length(); i++) {
    			if (from.charAt(i) != to.charAt(i)) {
    				diff += 1;
    				if (diff > 1)
    					return false;
    			}
    		}
    		return true;
    	}

  • 1
    D

    Yes, I used BFS by searching all words in Dict and then got timeout.
    Then I tried generating all possible next words instead of searching the whole dict and passed.
    I think real world situation is more important.


Log in to reply
 

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