---
title: "Word Ladder"
author: "KickCode"
date: "2016-02-11T02:46:40Z"
tags: []
categories: ["编程语言"]
slug: "word-ladder"
draft: false
lastmod: "2016-02-11T02:46:40Z"
id: 2276144
url: "https://kickcode.iteye.com/blog/2276144"
---

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = 
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

给定两个单词和一个单词集合，从一个单词变换到另一个单词，每次只能改变一个字母，并且变换后的单词都要在单词集合中，找出最少的变换次数。我们从beginWord开始，每个字符都可能有26种变换,我们用一个set来记录在wordlist中已经被访问过的单词，用path来记录走过的长度，如果变换后的单词与endword相同就返回path+1，如果不相同，看是否在wordlist中并且检查是否被访问过，然后更新beginSet，直到找到一条路，或者beginSet为空，返回0。代码如下：

```java

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        Set<String> beginSet = new HashSet<String>();
        Set<String> isVisited = new HashSet<String>();
        beginSet.add(beginWord);
        int path = 1;
        while(!beginSet.isEmpty()) {
            Set<String> tem = new HashSet<String>();
            for(String word : beginSet) {
                char[] c = word.toCharArray();
                for(int i = 0; i < c.length; i++) {
                    char oldChar = c[i];
                    for(char j = 'a'; j <= 'z'; j++) {
                        c[i] = j;
                        String s = new String(c);
                        if(s.equals(endWord))
                            return path + 1;
                        if(wordList.contains(s) && !isVisited.contains(s)) {
                            tem.add(s);
                            isVisited.add(s);
                        }
                    }
                    c[i] = oldChar;
                }
            }
            beginSet = tem;
            path ++;
        }
        return 0;
    }
}

```