beat 95% two end BFS java solution


  • 0
    D

    Idea comes from: https://discuss.leetcode.com/topic/17956/super-fast-java-solution-using-two-end-bfs

    To understand the code better, I change the original recursive version to iteration.

    public Set<String> getNeighbors(String cur, Set<String> dict) {
        Set<String> neighbors = new HashSet<>();
        char[] cArray = cur.toCharArray();
        for (int i = 0; i < cArray.length; ++i) {
            char ci= cArray[i];
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == ci) {
                    continue;
                }
                cArray[i] = c;
                String s = new String(cArray);
                if (dict.contains(s)) {
                    neighbors.add(s);
                }
            }
            cArray[i] = ci;
        }
        return neighbors;
    }
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        Set<String> s1 = new HashSet<>();
        Set<String> s2 = new HashSet<>();
        s1.add(beginWord);
        s2.add(endWord);
        
        // choose the set has the smaller size
        boolean isS1 = s1.size() < s2.size() ? true : false;
        Set<String> ss = isS1 ? s1 : s2;
        Set<String> ls = isS1 ? s2 : s1;
        int res = 0;
        while (!ss.isEmpty()){
            ++res;
            
            // remove for better performance and solve the visited problem
            wordList.removeAll(ss);
            
            // similar as queue.poll() in BFS
            Set<String> ns = new HashSet<>();
            
            for (String cur : ss) {
                if (ls.contains(cur)) {
                    return res;
                }
                for (String neighbor : getNeighbors(cur, wordList)) {
                        ns.add(neighbor);
                }
            }
            
            // choose the set has the smaller size
            isS1 = ns.size() < ls.size() ? true : false;
            ss = isS1 ? ns : ls;
            ls = isS1 ? ls : ns;
        }
        return 0;
    }

Log in to reply
 

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