TLE in Java BFS solution


  • 0
    J

    I got TLE, in this Java BFS solution. I can't find out where to improve, please advise.

    {
    public class Solution {
    class Node {
    String s;
    List<Node> nextSet = new ArrayList<Node>();
    boolean isEnd;
    boolean isVisited;

        public Node(String s) {
            this.s = s;
        }
    
        public void addNext(String str, Map<String, Node> map) {
                Node nd = map.get(str);
                if (nd != null && nextSet.contains(nd)) {
                    return;
                }
                if (isDiffOne(s, str)) {
                    if (nd == null) {
                        nd = new Node(str);
                        map.put(str, nd);
                    }
                    
                    nextSet.add(nd);
                    nd.nextSet.add(this);
                }
            
        }
    }
    
    boolean isDiffOne(String s1, String s2) {
        int diff = 0; 
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
            if (diff > 1) {
                return false;
            }
        }
        return diff == 1;
    }
    
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        Node startNd  = new Node(start);
        startNd.isVisited = true;
        Node endNd = new Node(end);
        endNd.isEnd = true;
        
        Map<String, Node> map = new HashMap<String, Node>();
        map.put(end, endNd);
        map.put(start, startNd);
        
        for (String s : dict) {
            Node nd = map.get(s);
            if (nd == null) {
                nd = new Node(s);
                map.put(s, nd);
                startNd.addNext(s, map);
            }
            
            for (String str : dict) {
                if (str != s) {
                    nd.addNext(str, map);
                }
            }
            nd.addNext(end, map);
        }
        List<List<String>> result = new ArrayList<List<String>>();
        
        int min[] = {Integer.MAX_VALUE};
        String breadcrumb[] = new String[dict.size() + 2];
        
        find(startNd, 0, breadcrumb, 0, min, result);
        return result;
    }
    void find(Node curr, int step, String breadcrumb[], int pos, int min[], List<List<String>> result) {
        if (step > min[0]) {
            return;
        }
        if (curr.isEnd) {
            min[0] = step;
            ArrayList<String> list = new ArrayList<String>();
            
            for (int i = 0; i < pos; i++) {
                list.add(breadcrumb[i]);
            }
            list.add(curr.s);
            result.add(list);
            return;
        } else if (step == min[0]) {
                return;
        }
        breadcrumb[pos] = curr.s;
        for (Node nd : curr.nextSet) {
            if (!nd.isVisited) {
                nd.isVisited = true;
                find(nd, step + 1, breadcrumb, pos + 1, min, result);
            }
        }
    }
    

    }
    }


Log in to reply
 

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