leetcode

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];