Can someone tell me what's wrong in my DFS approach.


  • 0
    P

    So I am basically finding all paths from current word and finding the minimum out of it. But it is failing on some test cases. Any help would be appreciated.

    public class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>();
        for(String str : wordList)
            set.add(str);
        int res =  wordLadder(beginWord, endWord, set, new HashMap<>(), new HashSet<>());
        return res == -1 ? 0 : res;
    }
    
    public int wordLadder(String beginWord, String endWord, Set<String> wordList, Map<String, Integer> seen, Set<String> visited) {
        if(beginWord.equals(endWord))
            return 1;
        if(seen.containsKey(beginWord))
            return seen.get(beginWord);
        int res = -1;
        for(int i = 0; i < beginWord.length(); i++) {
            for(int ch = 'a'; ch <= 'z'; ch++) {
                String str = beginWord.substring(0, i) + (char) ch + beginWord.substring(i + 1); 
                if(wordList.contains(str) && !visited.contains(str)) {
                    visited.add(str);
                    int next = wordLadder(str, endWord, wordList, seen, visited);
                    if( res == -1 && next != -1)
                        res = 1 + next;
                    else if(res != -1 && next != -1)
                        res = Math.min(res, 1 + next);
                    visited.remove(str);
                }
            }
        }
        seen.put(beginWord, res);
        return res;
      }
    
    }
    

Log in to reply
 

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