[LeetCode] 1871. Jump Game VII

轉自LeetCode

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

• i + minJump <= j <= min(i + maxJump, s.length - 1), and
• s[j] == '0'.

Return true if you can reach index s.length - 1 in s, or false otherwise.

 

Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

Example 2:

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

 

Constraints:

• 2 <= s.length <= 105
• s[i] is either '0' or '1'.
• s[0] == '0'
• 1 <= minJump <= maxJump < s.length

Solution

這題和 55. Jump Game 一樣，必須從後面往前面看

s[i] 可以抵達的條件是 s[i] = '0' ，且可以從 [i-maxJump, i-minJump] 這個範圍跳過來

因此用一個 counter 來記錄，在 [i-maxJump, i-minJump] 這個範圍內，有哪些點可以跳過來

一旦離開了這個範圍，也要從 counter 減掉

同時間也用 DP 的概念，來記錄之前可以抵達的點

kotlin

	class Solution {
	fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
	//dp[i] = true menas we can reach s[i]
	val dp = BooleanArray(s.length) {false}
	dp[0] = true
	// s[i] is reachable from the range of [i-maxJump, i-minJump] && s[i] == '0'
	var count = 0
	for(i in 1 until s.length) {
	if(i >= minJump && dp[i-minJump]) {
	++count
	}
	if(i > maxJump && dp[i-maxJump-1]) {
	--count
	}
	dp[i] = count > 0 && s[i] == '0'
	}
	return dp.last()
	}
	}

view raw jump_game_VII.kt hosted with ❤ by GitHub