leetcode

0 class Solution {

1 string crnt = string(9, '#');

2

3 int rec(const string &pattern, uint mask = 0, uint idx = 0) {

4 if (idx == pattern.size() + 1) return 1;

5

6 int start, end;

7 if (!idx) {

8 start = 1;

9 end = 9;

10 } else {

11 if (pattern[idx - 1] == 'I') {

12 start = (crnt[idx - 1] & 0xF) + 1;

13 end = 9;

14 } else {

15 start = 1;

16 end = (crnt[idx - 1] & 0xF) - 1;

17 }

18 }

19

20 for (int i = start; i <= end; i++) {

21 if (mask & (1 << i)) continue;

22 crnt[idx] = '0' + i;

23 if (rec(pattern, mask | (1 << i), idx + 1)) return 1;

24 }

25 return 0;

26 }

27

28 public:

29 string smallestNumber(const string &pattern) {

30 crnt.resize(pattern.size() + 1);

31 rec(pattern);

32 return crnt;

33 }

34 };