Provide a Java solution without change the List into HashSet beat 72%, 107ms


  • 1
    K

    public class Solution {

    private boolean[] visited;
    
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(wordList == null || wordList.size() == 0 || !wordList.contains(endWord)) return 0;
        Set<String> beginSet = new HashSet<>();
        beginSet.add(beginWord);
        Set<String> endSet = new HashSet<>();
        endSet.add(endWord);
        wordList.remove(beginWord);
        wordList.remove(endWord);
        visited = new boolean[wordList.size()];
        return findMinLength(beginSet, endSet, wordList, 2);
    }
    
    public int findMinLength(Set<String> set1, Set<String> set2, List<String> wordList, int length) {
        if(set1.size() == 0) return 0;
        Set<String> nextLevel = new HashSet<>();
        for(String s : set1) {
            for(String s2 : set2) {
                if(isOneLetterAway(s, s2)) return length;
            }
            for(int i = 0; i < wordList.size(); i++) {
                String compare = wordList.get(i);
                if(isOneLetterAway(s, compare) && !visited[i]) {
                    nextLevel.add(compare);
                    visited[i] = true;
                }
            }
        }
        if(nextLevel.size() > set2.size()) {
            return findMinLength(set2, nextLevel, wordList, length + 1);
        }else return findMinLength(nextLevel, set2, wordList, length + 1);
    }
    
    public boolean isOneLetterAway(String s1, String s2) {
        if(s1.length() != s2.length()) return false;
        if(s1.equals(s2)) return false;
        for(int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)) {
                while(i < s1.length() - 1) {
                    i++;
                    if(s1.charAt(i) != s2.charAt(i)) return false;
                }
            }
        }
        return true;
    }
    

    }


Log in to reply
 

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