2017 Update Bidirectional BFS - JAVA - 80%


  • 0
    9

    Just update (1) endWord need to be in the wordList condition and (2) argument change from Set to List
    ref1: https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms
    ref2: https://discuss.leetcode.com/topic/81291/updated-solution-based-on-new-requirement
    '''
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        if (!wordList.contains(endWord)){      // update
            return 0;
        }
     
        Set<String> wordSet = new HashSet<>(); //update
        for (String s : wordList) {
            wordSet.add(s);
        }
    
        
    // public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();
    
        int len = 1;
        int strLen = beginWord.length();
        HashSet<String> visited = new HashSet<String>();
    
        beginSet.add(beginWord);
        endSet.add(endWord);
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                Set<String> set = beginSet;
                beginSet = endSet;
                endSet = set;
            }
    
            Set<String> temp = new HashSet<String>();
            for (String word : beginSet) {
                char[] chs = word.toCharArray();
                for (int i = 0; i < chs.length; i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        char old = chs[i];
                        chs[i] = c;
                        String target = String.valueOf(chs);
    
                        if (endSet.contains(target)) {
                            return len + 1;
                        }
    
                        if (!visited.contains(target) && wordSet.contains(target)) {
                            temp.add(target);
                            visited.add(target);
                        }
                        chs[i] = old;
                    }
                }
            }
    
            beginSet = temp;
            len++;
        }
    
        return 0;
    }
    

    '''


Log in to reply
 

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