首页 > itarticle > 算法 WordLadder

算法 WordLadder

admin 1月 18, 2021 0

DP解法和图论解法，掌握DP的为准，参考图论解法。

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
39
40
41
42
43
44
 
package leetcode.BFSGraphic;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by cdx0312
 * 2018/4/8
 */
public class PerfectSquares_279 {
    public int numSquares(int n) {
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(n, 0));
        boolean[] visited = new boolean[n+1];
        visited[n] = true;
        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            int num = pair.num;
            int step = pair.step;
            if (num == 0)
                return step;
            for (int i = 1; num - i * i >= 0; i++) {
                if (!visited[num-i*i]) {
                    queue.offer(new Pair(num - i * i, step + 1));
                    visited[num - i * i] = true;
                }
            }
        }
        return n;
    }
    /**
     * num:当前数
     * step:n到num需要的步数
     */
    class Pair {
        int num;
        int step;
        public Pair(int num, int step) {
            this.num = num;
            this.step = step;
        }
    }
}

WordLadder

注释很清楚了。

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
39
40
41
 
package leetcode.BFSGraphic;

import java.util.*;

/**
 * Created by cdx0312
 * 2018/4/8
 */
public class WordLadder_127 {
    /*
        beginSet开始存放beginword，然后将经过一次变更字母之后可以编程的wordList中的字符串
        放入beginSet，直到出现变换成最终的字符串。
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList), qs = new HashSet<>(), qe = new HashSet<>(), vis = new HashSet<>();
        qs.add(beginWord);
        if (dict.contains(endWord))
            qe.add(endWord); // all transformed words must be in dict (including endWord)
        for (int len = 2; !qs.isEmpty(); len++) {
            Set<String> nq = new HashSet<>();
            for (String w : qs) {
                for (int j = 0; j < w.length(); j++) {
                    char[] ch = w.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == w.charAt(j))
                            continue; // beginWord and endWord not the same, so bypass itself
                        ch[j] = c;
                        String nb = String.valueOf(ch);
                        if (qe.contains(nb))
                            return len; // meet from two ends
                        if (dict.contains(nb) && vis.add(nb))
                            nq.add(nb); // not meet yet, vis is safe to use
                    }
                }
            }
            qs = (nq.size() < qe.size()) ? nq : qe; // switch to small one to traverse from other end
            qe = (qs == nq) ? qe : nq;
        }
        return 0;
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能