leetcode

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

0514.cpp (1360B)

      1 class Solution {
      2     static int left[101][26];
      3     static int right[101][26];
      4     static int dp[101][101];
      5 
      6     int rec(const string &ring, const string &key, int idx, int crnt) {
      7         if (idx == size(key)) return 0;
      8 
      9         if (key[idx] == ring[crnt]) return 1 + rec(ring, key, idx + 1, crnt);
     10         if (dp[idx][crnt] != -1) return dp[idx][crnt];
     11 
     12         const int n = size(ring);
     13         const int l = left[crnt][key[idx] - 'a'];
     14         const int r = right[crnt][key[idx] - 'a'];
     15 
     16         return dp[idx][crnt] = 1 + min(l + rec(ring, key, idx + 1, (crnt - l + n) % n),
     17                                        r + rec(ring, key, idx + 1, (crnt + r) % n));
     18     }
     19 
     20   public:
     21     int findRotateSteps(const string &ring, const string &key) {
     22         const int n = size(ring);
     23 
     24         memset(dp, 0xFF, sizeof(dp));
     25         memset(left, 0x00, sizeof(left));
     26         memset(right, 0x00, sizeof(right));
     27 
     28         for (int i = 0; i < n; i++) {
     29             for (int j = 1; j < n; j++) {
     30                 const int x = ring[(i + j) % n] - 'a';
     31                 const int y = ring[(i + n - j) % n] - 'a';
     32 
     33                 if (!right[i][x]) right[i][x] = j;
     34                 if (!left[i][y]) left[i][y] = j;
     35             }
     36         }
     37 
     38         return rec(ring, key, 0, 0);
     39     }
     40 };
     41 
     42 int Solution::left[101][26];
     43 int Solution::right[101][26];
     44 int Solution::dp[101][101];