Accepted Python/Java BFS + how to avoid TLE


  • 3

    Shortest path finding, when the weights are constant, as in this case = 1, BFS is the best way to go.
    Best way to avoid TLE is by using deque and popleft() .
    [Using list() and pop(0) is a linear operation in Python, resulting in TLE]

    Python:

        def openLock(self, deadends, target):
            marker, depth = 'x', 0
            visited, q, deadends = set(), deque(['0000', marker]), set(deadends)
    
            while q:
                node = q.popleft()
                if node == target:
                    return depth
                if node in visited or node in deadends:
                    continue
                if node == marker and not q:
                    return -1
                if node == marker:
                    q.append(marker)
                    depth += 1
                else:
                    visited.add(node)
                    q.extend(self.successors(node))
            return -1
    
        def successors(self, src):
            res = []
            for i, ch in enumerate(src):
                num = int(ch)
                res.append(src[:i] + str((num - 1) % 10) + src[i+1:])
                res.append(src[:i] + str((num + 1) % 10) + src[i+1:])
            return res
    

    Java:

    public static int openLock(String[] deadends, String target) {
            Queue<String> q = new LinkedList<>();
            Set<String> deads = new HashSet<>(Arrays.asList(deadends));
            Set<String> visited = new HashSet<>();
    
            int depth = 0;
            String marker = "*";
            q.addAll(Arrays.asList("0000", "*"));
            while(!q.isEmpty()) {
                String node = q.poll();
                if(node.equals(target))
                    return depth;
                if(visited.contains(node) || deads.contains(node))
                    continue;
                if(node.equals(marker) && q.isEmpty())
                    return -1;
                if(node.equals(marker)) {
                    q.add(marker);
                    depth += 1;
                } else {
                    visited.add(node);
                    q.addAll(getSuccessors(node));
                }
            }
            return depth;
        }
    
        private static List<String> getSuccessors(String str) {
            List<String> res = new LinkedList<>();
            for (int i = 0; i < str.length(); i++) {
                res.add(str.substring(0, i) + (str.charAt(i) == '0' ? 9 :  str.charAt(i) - '0' - 1) + str.substring(i+1));
                res.add(str.substring(0, i) + (str.charAt(i) == '9' ? 0 :  str.charAt(i) - '0' + 1) + str.substring(i+1));
            }
            return res;
        }
    

  • 1
    C

    @johnyrufus16 Nice, elegant solution.


  • 0

    Very simple and elegant solution


  • 0
    C

    @johnyrufus16 said in Accepted Python BFS + how to avoid TLE:

    deque

    Never realized that pop(0) takes O(N) in Python ... thanks !


  • 0
    V

    I like how you have just inserted marker into the queue to denote when a particular depth level is finished.


  • 1
    D

    Awesome solution! One thing to consider is that you might want to try taking the modulus of num +/- 1 as shown below:

    res.append(src[:i] + str((int(num) + 1) % 10) + src[i+1:])
    res.append(src[:i] + str((int(num) - 1) % 10) + src[i+1:])
    

    I don't think you would get much of performance boost but it might be more readable. Thanks again!


  • 0
    Z

    @johnyrufus16 Nice solution. Upvoted!


  • 1
    Z

    @charleszhou327 I personally found this link helpful when use python: https://wiki.python.org/moin/TimeComplexity, thought to share


  • 0

    @digitalnomd thanks, will update the solution based on your comment, I wasn't sure what -1 % n would produce, good that you pointed this out.


Log in to reply
 

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