127.md

#127. Word Ladder 题目链接

todo 超时

public class Solution {
       public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        HashMap<String ,Integer> record = new HashMap<>();

        wordList.add(beginWord);
        wordList.remove(endWord);
        int length = wordList.size() + 1;
        int count = 1;
        HashSet<String> intelrecord = new HashSet<>(Arrays.asList(endWord));
        while (length != wordList.size())
        {
            count ++;
            length = wordList.size();
            intelrecord = this.getNextWord(intelrecord, wordList);
            if (intelrecord.contains(beginWord))
                return count;
            this.removeWord(intelrecord, wordList);
        }
       return 0;
    }

    public void removeWord(HashSet<String> intelrecord, Set<String> wordList) {
        for (String intelword : intelrecord) {
            wordList.remove(intelword);
        }
    }

    public HashSet<String> getNextWord(HashSet<String> intelrecord, Set<String> wordList) {
        HashSet<String> nextWordList = new HashSet<>();
        for (String intelword : intelrecord) {
            for (String word : wordList) {
                if (this.isNextWord(intelword, word))
                    nextWordList.add(word);
            }
        }
        return nextWordList;
    }

    public boolean isNextWord(String curWord, String endWord) {
        int diffCount = 0;
        for (int i =0; i < curWord.length(); i++) {
            if (endWord.charAt(i) != curWord.charAt(i))
                diffCount++;
        }
        if (diffCount == 1)
            return true;
        return false;
    }
}