Can anyone help? Suspect something went wrong with the test case


  • 3
    L

    Input:
    "hit"
    "cog"
    ["hot","dot","dog","lot","log"]
    Output:
    [["hit","hot","lot","log","cog"],["hit","hot","dot","dog","cog"]]
    Expected:
    []

    Debugged for long time, did not find out what is wrong. Appreciate any help.
    
     public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            Set<String> cur  = new HashSet<>();
            cur.add(endWord);
            Set<String> next = new HashSet<>();
            Set<String> temp = null;
            
            Set<String> visited = new HashSet<>();
            visited.add(endWord);
            Set<String> visitedNextLev = new HashSet<>();
            
            Set<String> dic = new HashSet<String>(wordList);
            dic.add(beginWord);
            dic.add(endWord);
            Map<String, List<String>> map = new HashMap<>();
            
            while (!cur.isEmpty()){
                for (String word: cur){
                    if (word.equals(beginWord)){
                        return helper(beginWord, endWord, map);
                    }
                    
                    for (String nb: findNeighbors(word, dic, visited)){
                        map.putIfAbsent(nb, new ArrayList<String>());
                        map.get(nb).add(word);
                        next.add(nb);
                        visitedNextLev.add(nb);
                    }
                }
                
                cur.clear();
                temp = cur;
                cur = next;
                next = temp;
                
                visited.addAll(visitedNextLev);
                visitedNextLev.clear();
            }
            
            return new ArrayList<List<String>>(0);
        }
        
        private List<List<String>> helper(String st, String ed, Map<String, List<String>> map){
            List<List<String>> res = new LinkedList<>();
            List<String> list = new ArrayList<String>();
            list.add(st);
            res.add(list);
            
            String temp = null;
            while (true){
                list = res.get(0);
                if (list.get(list.size() - 1).equals(ed)){
                    break;
                }
                
                for (int i = res.size() - 1; i >= 0; i--){
                    list = res.remove(0);
                    
                    temp = list.get(list.size() - 1);
                    for (String next: map.get(temp)){
                        list.add(next);
                        res.add(new ArrayList<String>(list));
                        list.remove(list.size() - 1);
                    }
                }
            }
            
            return res;
        }
        
        private List<String> findNeighbors(String word, Set<String> dic, Set<String> visited){
            char[] wordArr = word.toCharArray();
            char temp;
            String tempS;
            
            List<String> res = new ArrayList<>();
            for (int i = 0; i < wordArr.length; i++){
                temp = wordArr[i];
                for (char c = 'a'; c <= 'z'; c++){
                    if (c != temp){
                        wordArr[i] = c;
                        tempS = new String(wordArr);
                        if (!visited.contains(tempS) && dic.contains(tempS)){
                            res.add(tempS);
                        }
                    }
                }
                
                wordArr[i] = temp;
            }
            return res;
        }
    

  • 0
    D

    I got the exact same test case. It works fine with "Run Code".

    Run Code Result:×
    
    Your input
    
    "hit"
    "cog"
    ["hot","dot","dog","lot","log","cog"]
    Your answer
    
    [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
    Expected answer
    
    [["hit","hot","lot","log","cog"],["hit","hot","dot","dog","cog"]]
    

    But it's somehow broken with "Submit Solution":

    Submission Result: Wrong Answer More Details 
    
    Input:
    "hit"
    "cog"
    ["hot","dot","dog","lot","log"]
    Output:
    [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
    Expected:
    []
    

  • 0

    said in Can anyone help? Suspect something went wrong with the test case:

    "cog"
    ["hot","dot","dog","lot","log"]

    ["hot","dot","dog","lot","log"] doesn't contain "cog".


  • 0

    @david120
    these test cases are different.


Log in to reply
 

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