Test case not good enough?


  • 0
    Z

    I have the following code got accepted:

    public int ladderLength(String start, String end, HashSet<String> dict) {
        if(start.length() == 0 && end.length() == 0) return 0;
        
        //BFS
        Queue<String> queue = new LinkedList<String>();
        queue.add(start);
        Queue<Integer> distance = new LinkedList<Integer>();
        distance.add(1);
        HashSet<String> visited = new HashSet<String>();
        while(!queue.isEmpty()){
            String cur = queue.poll();
            int dis = distance.poll();
            if(cur.equals(end)) return dis;
            
            //add all strings with one character different from current string into the queue
            for(int i = 0; i < cur.length(); i++){
                char[] c = cur.toCharArray();
                for(int j = 'a'; j <= 'z'; j++){
                    c[i] = (char)j;
                    String newString = new String(c);
                    if(dict.contains(newString) && !visited.contains(newString)){
                        visited.add(newString);
                        queue.add(newString);
                        distance.add(dis+1);
                    }
                }
                
            }
            
            
            //this is not very efficient
            // Iterator<String> it = dict.iterator();
            // while(it.hasNext()){
            //     String s = it.next();
            //     if(diff(cur, s) == 1 && !visited.contains(s)){
            //         queue.add(s);
            //         distance.add(dis+1);
            //         visited.add(s);
            //     }
            // }
            // if(diff(cur, end) == 1) return dis+1;
        }
        return 0;
    }
    

    I used BFS, for each String in the queue, I put all the unvisited Strings in the dictionary into the queue. However, I did not check the case when String end is not in the dictionary. Consider the following case:

    start: hit end: hog dict:["hot"];

    My code should fail because it never adds "hog" into the queue so it is never visited.


  • 0
    S

    Hi! Are you wondering about the correctness of the test cases? Note that "each intermediate word must exist in the dictionary", but there is no similar requirements for start word or end word, so I think you should improve your code to fit this case.


Log in to reply
 

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