Missing test case


  • 1
    D

    If the end string is not in the dictionary, like what is given in the problem statement, the distance doesn't necessarily need to be 0.
    Note: A simple solution is to add end to dictionary in my solution. But still it would be nice to catch it as I see from quite a number of solutions online the case is missing.

    Junit test case:

    @Test
    public void testSolution() {
    	Solution sol1 = new Solution(); 
    	assertEquals(5, sol1.ladderLength("hit", "cog", 
    			new HashSet<String>(Arrays.asList("hot","dot","dog","lot","log"))));
    }
    

    Accepted buggy solution:

    public class Solution {
        public int ladderLength(String start, String end, HashSet<String> dict) {
            if (dict == null || dict.isEmpty()) return 0;
            
            Deque<Node> workQueue = new ArrayDeque<Node>();
            workQueue.offerFirst(new Node(start,1));
            
            int result = 0;
            if(end.length()*26>dict.size()/2) {
                result = doBfsWithDict(workQueue, end, dict);
            } else {
                result = doBfsWithEnumeration(workQueue, end, dict);
            }
            return result;
        }
       
        private int doBfsWithEnumeration(Deque<Node> workQueue, String end, HashSet<String> dict) {
            while (!workQueue.isEmpty()) {
                if(dict.isEmpty()) return 0;
                Node cur = workQueue.pollFirst();
                
                char[] word = cur.word.toCharArray();
                for (int i=0; i<end.length(); i++) {
                    char enumerate = word[i];
                    for(char c='a'; c<='z'; c++) {
                        if(c!=enumerate) {
                            word[i] = c;
                            String s = new String(word);
                            if (dict.contains(s)) {
                                if(s.equals(end)) {//notice we should not look ahead by checking distance here
                                    return cur.distance+1;
                                } else {
                                    workQueue.offerLast(new Node(s, cur.distance+1));//offerLast to queue
                                    dict.remove(s);//if dict is final, keep a visited hashset
                                }
                            }
                        }
                    }
                    word[i]=enumerate;
                }
            }
            return 0;
        }
        
        private int doBfsWithDict(Deque<Node> workQueue, String end, HashSet<String> dict) {
            while (!workQueue.isEmpty()) {
                if(dict.isEmpty()) return 0;
                Node cur = workQueue.pollFirst();
                List<String> toRemove = new ArrayList<String>();
                for (String s: dict) {
                    if(getDistance(cur.word, s) == 1) {
                        if(s.equals(end)) {//notice we should not look ahead by checking distance=1 here
                        // example a,c and [a,b,c] (result=2, not 3)
                            return cur.distance+1;
                        } else {
                            workQueue.offerLast(new Node(s, cur.distance+1));//offerLast to queue
                            toRemove.add(s);
                        }
                    }
                }
                dict.removeAll(toRemove);
            }
            return 0;
        }
        
        // return number of difference characters between given and goal
        // assume equal positive length
        private int getDistance(String given, String goal) {
            int diff = 0;
            for(int i=0; i<given.length(); i++) {
                if(given.charAt(i) != goal.charAt(i)) diff++;
            }
            return diff;
        }
        
        private class Node {
            String word;
            int distance;
            
            Node(String s, int n) {
                word = s;
                distance = n;
            }
        }
    }

Log in to reply
 

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