leetcode

Solution to some Leetcode problems written in C++

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

0514.cpp (1360B)

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