leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0664.cpp (644B)

0 class Solution { 1 int dp[101][101]; 2 int rec(const string &s, int l, int r) { 3 if (dp[l][r] != -1) return dp[l][r]; 4 int res = s.size(), j = -1; 5 for (int i = l; i < r; i++) { 6 if (s[i] != s[r] && j == -1) j = i; 7 if (j != -1) res = min(res, 1 + rec(s, j, i) + rec(s, i + 1, r)); 8 } 9 return dp[l][r] = j != -1 ? res : 0; 10 } 11 12 public: 13 Solution() { memset(dp, 0xFF, sizeof(dp)); } 14 int strangePrinter(string &s) { 15 int j = 1; 16 for (int i = 1; i < s.size(); i++) 17 if (s[i] != s[i - 1]) s[j++] = s[i]; 18 19 return rec(s, 0, j - 1) + 1; 20 } 21 };