Untitled
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