Задача: 403. Frog Jump
Сложность: hard

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true

👨‍💻 Алгоритм:

1⃣Инициализация и структура данных
Создайте набор для хранения всех камней для быстрого доступа.
Используйте динамическое программирование с помощью словаря для отслеживания достижимых позиций и возможных прыжков.

2⃣Итерация по камням
Пройдитесь по каждому камню и для каждого возможного прыжка (k-1, k, k+1) проверьте, если он ведет на существующий камень.
Если такой камень существует, добавьте его в набор возможных прыжков.

3⃣Проверка достижения последнего камня
Если можно достичь последний камень с помощью одного из возможных прыжков, верните True.
Если после всех итераций последний камень не достигнут, верните False.Формирование результата:
Постройте итоговое число из цифр в стеке и удалите ведущие нули.

😎 Решение:

class Solution {
    func canCross(_ stones: [Int]) -> Bool {
        var dp = [Int: Set<Int>]()
        for stone in stones {
            dp[stone] = Set<Int>()
        }
        dp[0]?.insert(0)
        
        for stone in stones {
            for jump in dp[stone]! {
                for step in jump - 1...jump + 1 {
                    if step > 0, let _ = dp[stone + step] {
                        dp[stone + step]?.insert(step)
                    }
                }
            }
        }
        
        return !(dp[stones.last!]!.isEmpty)
    }
}

Ставь 👍 и забирай 📚 Базу знаний