Сложность: hard
Существует странный принтер с двумя особыми свойствами:
Принтер может печатать последовательность одного и того же символа за раз.
На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы.
Дана строка s. Верните минимальное количество ходов, необходимых для её печати.
Пример:
Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".
👨💻 Алгоритм:
1⃣Инициализация и подсчет:
Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1].
2⃣Динамическое программирование:
Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим.
В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов.
3⃣Возврат результата:
Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки.
😎 Решение:
class Solution {
func strangePrinter(_ s: String) -> Int {
let n = s.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
let chars = Array(s)
for length in 1...n {
for i in 0...(n - length) {
let j = i + length - 1
dp[i][j] = (i == j) ? 1 : dp[i][j - 1] + 1
for k in i..<j {
if chars[k] == chars[j] {
dp[i][j] = min(dp[i][j], dp[i][k] + (dp[k + 1][j - 1] if k + 1 <= j - 1 else 0))
}
}
}
}
return dp[0][n - 1]
}
}Ставь 👍 и забирай 📚 Базу знаний