Участник:UlitinAleksander/strange-printer

Материал из DISCOPAL
< Участник:UlitinAleksander
Версия от 19:34, 2 декабря 2020; UlitinAleksander (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Java

https://leetcode.com/problems/strange-printer/submissions/


class Solution {
    public int strangePrinter(String s) {
        int len = s.length();
        t_ = new int[len][len];
        return turn(s.toCharArray(), 0, len-1);
    }
 
    public int turn(char[] s, int i, int j) {
        if (i > j) return 0;
        if (t_[i][j] > 0) return t_[i][j];
 
        int ans = turn(s, i, j-1) + 1;
 
        for (int k = i; k < j; ++k) {
            if (s[k] == s[j]) 
                ans = Math.min(ans, turn(s, i, k) + turn(s, k+1, j-1));
        }
 
        t_[i][j] = ans;
 
        return t_[i][j];
    }
 
    private int[][] t_;
}