leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0664.cpp (644B)

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