Frog Jump

Problem Id: 403 Difficulty: Hard


Intuition

Solution


class Solution:
    def _dfs(self, last, step):
        if step == 0:
            return False
        if last == self.target:
            return True

        for next_step in range(max(step - 1, 1), step + 2):
            next_stone = next_step + last
            if next_step == 0:
                continue
            if next_stone not in self.stones:
                continue
            if next_step in self.stones[last]:
                continue
            self.stones[last].add(next_step)
            if self._dfs(next_stone, next_step):
                return True
        return False

    def canCross(self, stones: List[int]) -> bool:
        if len(stones) == 1:
            return True
        elif 1 not in stones:
            return False

        self.stones = {stone: set() for stone in stones}
        self.target = stones[-1]
        return self._dfs(1, 1)


class TestSolution(unittest.TestCase):
    def test_true(self):
        self.assertTrue(Solution().canCross([0,1,3,5,6,8,12,17]))
        self.assertTrue(Solution().canCross([0,1]))

    def test_false(self):
        self.assertFalse(Solution().canCross([0,1,2,3,4,8,9,11]))
        self.assertFalse(Solution().canCross([0,2]))


if __name__ == '__main__':
    unittest.main()