Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.1 kB
3
Indexable
Never
class Solution {
public:
    int n;
    int dp[102][102];
    string str;
    int strangePrinter(string s) {
        str = eraseDuplicates(s);
        
        for(int i=0;i<102;i++) {
            for(int j=0;j<102;j++) {
                dp[i][j] = -1;
            }
        }
        
        int ans = solve(0 , str.size()-1);
        return ans;
    }
    
    int solve(int start, int end) {
        if(start > end)return 0;
        
        if(dp[start][end]!=-1) return dp[start][end];
        
        int minimumTurns = 1 + solve(start + 1, end);
        
        for(int i=start+1;i<=end;i++) {
            if(str[i] == str[start]) {
                minimumTurns = min(minimumTurns, solve(start , i - 1) + solve(i + 1 , end));
            }
        }
        
        return dp[start][end] = minimumTurns;
    }
    
    string eraseDuplicates(string s) {
        string unique;
        
        unique+=s[0];
        
        for(int i=1;i<s.size();i++) {
            if(s[i]!=s[i-1]) {
                unique+=s[i];
            }
        }
        
        return unique;
    }
};
Leave a Comment