Simple Java Solution O(n), without dp
Use a queue to store the reachable indices from previous indices traversed. (Kinda like BFS).\n2. At each iteration pop an element from the queue, calculate the
1. Use a queue to store the reachable indices from previous indices traversed. (Kinda like BFS).\n2. At each iteration pop an element from the queue, calculate the min & max reachable indices from this popped index.\n3. [Now comes tricky part] We only push indices which are have value == \'0\'.\n4. We are keeping a variable called "far" which stores, till how far in the array we have discovered all the reachable indices. This reduces the number of indices we need to traverse in step 2.\n5. Now all that is left is to see if while traversing the queue, can we reach our destinatin or not!\n\nhappy coding!\n\nclass Solution {\n\n    public boolean canReach(String s, int minJump, int maxJump) {\n        int n=s.length();\n        Queue<Integer> q=new LinkedList();\n        if(s.charAt(n-1)==\'1\') // can\'t reach destination\n            return false;\n        q.offer(0);\n        int far=0;\n        while(!q.isEmpty()){\n            int i=q.poll();\n            int min=i+minJump;\n            int max=i+maxJump;\n           \n            for(int j=Math.max(min,far);j<=max && j<n;j++){\n                if(s.charAt(j)==\'0\'){    \n                    q.offer(j);\n                    if(j==n-1)\n                        return true; //reached at destination\n                }            \n            }\n            far=Math.max(far, max);\n        }\n        return false; \n    }\n}
['Queue', 'Java']