Java solution - no HashSet conversion from List


  • 1
    D
    public class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Set<String> set = new HashSet<>();
            set.add(beginWord);
            int n = wordList.size();
            boolean[] visited = new boolean[n];
            Arrays.fill(visited, false);
            int len = 0;
            while (!set.isEmpty()) {
                len += 1;
                Set<String> newSet = new HashSet<>();
                for (String s : set) {
                    if (s.equals(endWord))
                        return len;
                    for (int i = 0; i < n; i++) {
                        if (!visited[i]) {
                            String word = wordList.get(i);
                            if (oneLetterAway(s, word)) {
                                newSet.add(word);
                                visited[i] = true;
                            }
                        }
                    }
                }
                set = newSet;
            }
            return 0;
        }
        private boolean oneLetterAway(String a, String b) {
            if (a.length() != b.length())
                return false;
            if (a.equals(b))
                return false;
            
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    return a.substring(i+1).equals(b.substring(i+1));
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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