DEV Community

Kardel Chen
Kardel Chen

Posted on

3 3

Leetcode 403 Frog Jump

from typing import List


class Solution:
    def canCross(self, stones: List[int]) -> bool:
        N = len(stones)
        d = {}
        if stones[1] != 1: # if we cannot jump at initial place, it definitely False
            return False
        # build value-index mapping
        for i, stone in enumerate(stones):
            d[stone] = i
        # dp is the number of jumps to location i
        # for example, we can only jump to pos 1 with 1 units
        # if we can jump to pos X for {a, b, c} units, it means that we can jump to X for a, b, c units
        # it also means that from pos X, we can jump for <a-1, a, a+1, b-1, b, b+1, c-1, c, c+1> units. 
        dp = [{0}, {1}]
        for i in range(2, N):
            dp.append(set())
        for i in range(1, N):
            s = stones[i]
            for k in dp[i]:
                # do jump
                # if k-1 is ok for position stones[i], jump and add to dp
                if s + k - 1 in d and k - 1 != 0:
                    dp[d[s + k - 1]].add(k - 1)
                # if k is ok for position stones[i], jump and add to dp
                if s + k in d and k != 0:
                    dp[d[s + k]].add(k)
                # if k+1 is ok for position stones[i], jump and add to dp
                if s + k + 1 in d and k + 1 != 0:
                    dp[d[s + k + 1]].add(k + 1)
        return len(dp[-1]) != 0
Enter fullscreen mode Exit fullscreen mode

Jetbrains image

Don’t Become a Data Breach Headline

57% of organizations have suffered from a security incident related to DevOps toolchain exposures. Is your CI/CD protected? Check out these nine practical tips to keep your CI/CD secure—without adding friction.

Learn more

Top comments (0)

Sentry image

Make it make sense

Only the context you need to fix your broken code with Sentry.

Start debugging →

👋 Kindness is contagious

Explore a trove of insights in this engaging article, celebrated within our welcoming DEV Community. Developers from every background are invited to join and enhance our shared wisdom.

A genuine "thank you" can truly uplift someone’s day. Feel free to express your gratitude in the comments below!

On DEV, our collective exchange of knowledge lightens the road ahead and strengthens our community bonds. Found something valuable here? A small thank you to the author can make a big difference.

Okay