C++ || Java || Bi-directional BFS || O(n)
Intuition\nBFS and DFS are relatively intuitive solutions to this problem. However, as it turns out, standard BFS and DFS both result in Time Limit Exceeded (TL
# Intuition\nBFS and DFS are relatively intuitive solutions to this problem. However, as it turns out, standard BFS and DFS both result in Time Limit Exceeded (TLE), thus a more optimal approach is necessary.\n\n# Approach\nNotice that BFS/DFS can be done in either direction (either left to right or vice versa). We can exploit this fact by performaing BFS in both directions at the same time, and terminating when\n\n- both searches \'meet\', or\n- either search hits a dead end\n\nOne huge advantage is that if there is a dead end, bi-directional BFS can hit it much faster than a standard BFs.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code (C++)\n```\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump) {\n        return s[s.size() - 1] == \'0\' && biBfs(s, minJump, maxJump);\n    }\n\nprivate:\n    bool biBfs(string& s, const int minJump, const int maxJump) {\n        int n = s.size();\n        queue<int> q, q2;\n        vector<bool> visited(n, false), visited2(n, false);\n\n        q.push(0);\n        visited[0] = true;\n        q2.push(n - 1);\n        visited2[n - 1] = true;\n\n        // stop searching the moment either bfs hits a dead end\n        while (!q.empty() && !q2.empty()) {\n            int curr = q.front(), curr2 = q2.front();\n            q.pop();\n            q2.pop();\n\n            for (int dst = min(curr + maxJump, n - 1); dst >= curr + minJump; dst--) {\n                if (s[dst] == \'0\' && !visited[dst]) {\n                    if (visited2[dst]) // found a common destination\n                        return true;\n                    q.push(dst);\n                    visited[dst] = true;\n                }\n            }\n\n            for (int dst = max(curr2 - maxJump, 0); dst <= curr2 - minJump; dst++) {\n                if (s[dst] == \'0\' && !visited2[dst]) {\n                    if (visited[dst]) // found a common destination\n                        return true;\n                    q2.push(dst);\n                    visited2[dst] = true;\n                }\n            }\n        }\n        return false;\n    }\n};\n\n```\n\n# Code (Java)\n```\nclass Solution {\n    public boolean canReach(String s, int minJump, int maxJump) {\n        return s.charAt(s.length() - 1) == \'0\' && biBfs(s, minJump, maxJump);\n    }\n\n    private boolean biBfs(String s, int minJump, int maxJump) {\n        int n = s.length();\n        Deque<Integer> q = new ArrayDeque<>();\n        Deque<Integer> q2 = new ArrayDeque<>();\n        boolean[] visited = new boolean[n];\n        boolean[] visited2 = new boolean[n];\n\n        q.add(0);\n        visited[0] = true;\n        q2.add(n - 1);\n        visited2[n - 1] = true;\n\n        // stop searching the moment either bfs hits a dead end\n        while (!q.isEmpty() && !q2.isEmpty()) {\n            int curr = q.poll(), curr2 = q2.poll();\n\n            for (int dst = Math.min(curr + maxJump, n - 1); dst >= curr + minJump; dst--) {\n                if (s.charAt(dst) == \'0\' && !visited[dst]) {\n                    if (visited2[dst]) // found a common destination\n                        return true;\n                    q.add(dst);\n                    visited[dst] = true;\n                }\n            }\n\n            for (int dst = Math.max(curr2 - maxJump, 0); dst <= curr2 - minJump; dst++) {\n                if (s.charAt(dst) == \'0\' && !visited2[dst]) {\n                    if (visited[dst]) // found a common destination\n                        return true;\n                    q2.add(dst);\n                    visited2[dst] = true;\n                }\n            }\n        }\n        return false;\n    }\n}\n\n```
['Breadth-First Search', 'C++', 'Java']