LeetCode刷题记148

126. 单词接龙 II

题目

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ans = new ArrayList();
        int l = wordList.size();
        if (l == 0) return ans;
        int l_w = wordList.get(0).length();
        int[][] g = new int[l + 1][l + 1];
        for (int i = 0; i < l + 1; i ++) {
            for (int j = 0; j < l + 1; j ++) {
                g[i][j] = Integer.MAX_VALUE;
            }
        }

        int end = -1;
        for (int i = 0; i < l; i ++) {
            String s1 = wordList.get(i);
            int cnt = 0;
            int cnt2 = 0;
            for (int k = 0; k < l_w; k ++) {
                if (s1.charAt(k) != beginWord.charAt(k)) cnt ++;
                if (s1.charAt(k) != endWord.charAt(k)) cnt2 ++;
            }
            if (cnt == 1) {
                g[0][i + 1] = 1;
                g[i + 1][0] = 1;
            }
            if (cnt2 == 0) end = i + 1;
            for (int j = i + 1; j < l; j ++) {
                String s2 = wordList.get(j);
                cnt = 0;
                for (int k = 0; k < l_w; k ++) {
                    if (s1.charAt(k) != s2.charAt(k)) cnt ++;
                }
                if (cnt == 1) {
                    g[i+1][j+1] = 1;
                    g[j+1][i+1] = 1;
                }
            }
        }
        if (end == -1) return ans;

        int num = l + 1;
        int[] d = new int[num];
        // int[] pre = new int[num];
        // Arrays.fill(pre, -1);
        boolean[] v = new boolean[num];
        for (int i = 0; i < num; i ++) {
            d[i] = Integer.MAX_VALUE;
        }
        List<Integer>[] pre = new ArrayList[num];
        Queue<Integer> q = new LinkedList<Integer>();
        d[0] = 0;
        q.add(0);
        v[0] = true;
        while (q.isEmpty() == false) {
            int cur = q.poll();
            for (int i = 0; i < num; i ++) {
                if (g[cur][i] < Integer.MAX_VALUE) {
                    if (v[i] == false) {
                        v[i] = true;
                        q.add(i);
                    }
                    // d[i] = Math.min(d[i], g[cur][i] + d[cur]);
                    if (d[i] >= g[cur][i] + d[cur]) {
                        if (pre[i] == null) pre[i] = new ArrayList<Integer>();
                        pre[i].add(cur);
                        d[i] = g[cur][i] + d[cur];
                    }
                }
            }
        }
        // int lll = Math.max(d[end] + 1, 0);
        
        Arrays.fill(v, false);
        F(ans, end, beginWord, pre, new ArrayList<String>(), wordList, v);
        
        return ans;
    }

    public void F(List<List<String>> ans, int cur, String beginWord, List<Integer>[] pre, List<String> path, List<String> wordList, boolean[] v) {
        if (cur == 0) {
            List<String> _ans = new ArrayList<String>();
            _ans.addAll(path);
            _ans.add(beginWord);
            Collections.reverse(_ans);
            ans.add(_ans);
            return;
        }
        if (pre[cur] == null) return;
        for (Integer i : pre[cur]) {
            if (!v[i]) {
                v[i] = true;
                List<String> tmp = new ArrayList<String>();
                tmp.addAll(path);
                tmp.add(wordList.get(cur - 1));
                F(ans, i, beginWord, pre, tmp, wordList, v);
                v[i] = false;
            }
        }

    }
}

我写的这都是什么鬼，这么混乱。
不过大概看了一眼官方解答，好像那个也是把路径全部存下来。
好烦躁，手上的项目做不出来。。。
5/3
148/150