Java - DFS, BFS + sliding window | O(n) time and space
\n#### DFS + sliding window\n A sliding window approach is used to visit only unvisited nodes \n Variable "farthestVisitedIndex" keeps track of the index of the
\n#### DFS + sliding window\n* A sliding window approach is used to visit only unvisited nodes \n* Variable "farthestVisitedIndex" keeps track of the index of the farthest visited node  \n* Hence our sliding window starts from Max(farthestVisitedIndex + 1, index + minJump) and extends till Min(index  + maxJump, last index of the string), where index is index of the character in the string that is currently being processed\n* This gurantees that we visit each node only once giving us the time complexity of O(N)\n* Time: O(N)\n* Space: O(N)\n```\nclass Solution {\n    int minJump, maxJump;\n    String s;\n    int farthestVisitedIndex = 0;\n    public boolean canReach(String s, int minJump, int maxJump) {\n        this.minJump = minJump;\n        this.maxJump = maxJump;\n        this.s = s;\n        if(s.charAt(s.length() - 1) != \'0\' || minJump >= s.length()) return false;\n        return canReach(0, minJump);\n    }\n    \n    public boolean canReach(int index, int windowStart) {\n        if(index == s.length() - 1) return true;\n        int windowEnd = Math.min(index + maxJump, s.length() - 1);\n        farthestVisitedIndex = windowEnd;\n        for(int i = windowStart; i <= windowEnd; i++) {\n            if(s.charAt(i) == \'0\') {\n                if(canReach(i, Math.max(farthestVisitedIndex + 1, i + minJump))) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n}\n```\n\n#### BFS + sliding window\n* Same explanation as above applies for sliding window logic\n* Time: O(N)\n* Space: O(N)\n```\nclass Solution {\n    public boolean canReach(String s, int minJump, int maxJump) {\n        if(s.charAt(s.length() - 1) != \'0\' || minJump >= s.length()) return false;\n        int farthestVisitedIndex = 0;\n        Queue<Integer> q = new ArrayDeque<>();\n        q.offer(0);\n        while(!q.isEmpty()) {\n            int index = q.poll();\n            if(index == s.length() - 1) return true;\n            int windowStart = Math.max(index + minJump, farthestVisitedIndex + 1);\n            int windowEnd = Math.min(index + maxJump, s.length() - 1);\n            farthestVisitedIndex = windowEnd;\n            for(int i = windowStart; i <= windowEnd; i++) {\n                if(s.charAt(i) == \'0\') q.offer(i);\n            }\n        }\n        return false;\n    }\n}\n```\n
['Depth-First Search', 'Breadth-First Search', 'Sliding Window', 'Java']