902ms Java Accepted solutiuon


  • 0
    D
    public class Solution {
        int dist( String x, String y ) {
            int k = 0;
            for ( int i = 0; i < x.length(); ++i )
                if ( x.charAt(i) != y.charAt(i) && (++k) >= 2 )
                    return 2;
            return k;
        }
        private final static int oo = (1<<29);
        List<String> L;
        int D,src,sink;
        int []distance,d;
        boolean []seen = new boolean[1<<20];
        boolean [][]g;
        int [][]adj, tr;
        void generate( int x, int costSoFar, int []idx, List<List<String>> lst ) {
            if ( x == sink ) {
                if ( costSoFar == D ) {
                    List<String> l = new ArrayList<>();
                    l.add(L.get(src));
                    for ( int j = 0; j < costSoFar; ++j )
                        l.add(L.get(idx[j]));
                    lst.add(l);
                }
                return ;
            }
            if ( costSoFar >= D || d[x] == +oo || distance[x] == +oo || d[x]+distance[x] != D ) return ;
            for ( int y,i = 0; i < adj[x].length && distance[adj[x][i]] < +oo && d[x]+distance[adj[x][i]] <= D; ++i )
                if ( !seen[y = adj[x][i]] && distance[y] < +oo && costSoFar+distance[y] <= D ) {
                    idx[costSoFar] = y;
                    seen[y] = true ;
                    generate(y,costSoFar+1,idx,lst);
                    seen[y] = false ;
                }
        }
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            L = wordList;
            if ( wordList.contains(beginWord) ) src = wordList.indexOf(beginWord);
            else {
                wordList.add(beginWord);
                src = wordList.indexOf(beginWord);
            }
            if ( wordList.contains(endWord) ) sink = wordList.indexOf(endWord);
            else return new ArrayList<>();
            int i,j,k,n = wordList.size();
            g = new boolean[n][n];
            for ( i = 0; i < n; ++i )
                for ( j = i+1; j < n; ++j )
                    g[i][j] = g[j][i] = dist(wordList.get(i),wordList.get(j))==1;
            adj = new int[n][];
            for ( i = 0; i < n; ++i ) {
                for ( j = k = 0; k < n; ++k )
                    if ( g[i][k] ) ++j;
                adj[i] = new int[j];
                for ( k = 0, j = 0; j < n; ++j )
                    if ( g[i][j] )
                        adj[i][k++] = j;
            }
            Queue<Integer> q = new LinkedList<>();
            d = new int[n];
            for ( i = 0; i < n; d[i++] = +oo );
            for ( q.add(src), d[src] = 0; !q.isEmpty(); )
                for ( i = q.poll(), k = 0; k < adj[i].length; ++k )
                    if ( d[j=adj[i][k]] > d[i]+1 ) {
                        d[j] = d[i]+1;
                        q.add(j);
                    }
            if ( (D=d[sink]) == +oo )
                return new ArrayList<>();
            distance = new int[n];
            for ( i = 0; i < n; ++i ) distance[i] = +oo;
            for ( q.add(sink), distance[sink] = 0; !q.isEmpty(); ) 
                for ( i = q.poll(), k = 0; k < adj[i].length; ++k )
                    if ( distance[j=adj[i][k]] > distance[i]+1 ) {
                        distance[j] = distance[i]+1;
                        q.add(j);
                    }
            for ( i = 0; i < n; ++i ) {
                for ( boolean flag = true ; flag; )
                    for ( flag = false, k = 0; k < adj[i].length-1; ++k )
                        if ( distance[adj[i][k]] > distance[adj[i][k+1]] ) {
                            int tmp = adj[i][k]; adj[i][k] = adj[i][k+1]; adj[i][k+1] = tmp;
                            flag = true ;
                        }
            }
            List<List<String>> res = new ArrayList<>();
            seen[src] = true ;
            int []idx = new int[D];
            generate(src,0,idx,res);
            seen[src] = false ;
            return res;
        }
    }
    

    I believe the problem is NP, so the optimizations in this problem can be pretty much ad hoc, and the center of gravity is certainly two-end BFS, and one cannot in principle do better than backtracking when generating the paths.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.