首页 > itarticle > leetcode笔记：127. word ladder

leetcode笔记：127. word ladder

admin 11月 14, 2020 0

# Title Difficulty Topic
127 Word Ladder Medium Breadth-first Search

Description

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:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

1
2
3
4
5
6
7
8
9
 
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

1
2
3
4
5
6
7
8
 
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

单向BFS

单向BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
class  {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)) return 0;
        Set<String> wordSet = new HashSet<>(wordList);
        Queue<String> queue = new LinkedList<>();
        int level = 0;
        queue.offer(beginWord);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i=0; i<size; i++) {
                String s = queue.poll();
                if(s.equals(endWord)) return level + 1;
                for(int j=0; j<s.length(); j++) {
                    char[] ch = s.toCharArray();
                    for(char k='a'; k<='z'; k++) {
                        ch[j]=k;
                        String temp = String.valueOf(ch);
                        if(!temp.equals(s) && wordSet.contains(temp)) {
                            queue.add(temp);
                            wordSet.remove(temp);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
}

时间复杂度为$$O(n*26^l)$$，其中$n$表示wordList的长度，$l$表示beginWord的长度，空间复杂度$$O(n)$$。

双向BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
class  {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)) return 0;
        Set<String> wordSet = new HashSet<>(wordList);
        Set<String> s1 = new HashSet<>();
        s1.add(beginWord);
        Set<String> s2 = new HashSet<>();
        s2.add(endWord);
        int level = 1;
        while(!s1.isEmpty() && !s2.isEmpty()) {
            
            if(s1.size() > s2.size()) {
                Set<String> s1Tmp = s1;
                s1 = s2;
                s2 = s1Tmp;
            }
            
            Set<String> tmp = new HashSet<>();
            for(String word : s1) {
                for(int i=0; i<word.length(); i++) {
                    char[] ch = word.toCharArray();
                    for(char j='a'; j<='z'; j++) {
                        ch[i] = j;
                        String sTmp = new String(ch);
                        if(s2.contains(sTmp)) return level + 1;
                        if(wordSet.contains(sTmp)) {
                            tmp.add(sTmp);
                            wordSet.remove(sTmp);
                        }
                    }
                }
            }
            s1 = tmp;
            level++;
        }
        return 0;
    }
}

时间复杂度为$$O(n*26^{l/2})$$，其中$n$表示wordList的长度，$l$表示beginWord的长度，空间复杂度$$O(n)$$。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能