leetcode

0 class Solution {

1 vector<char> next[6][6];

2 unordered_map<string, bool> seen;

3

4 bool rec(const string &bottom) {

5 if (bottom.size() == 1) return true;

6 if (seen.count(bottom)) return seen[bottom];

7

8 vector<string> prev, crnt;

9 for (int i = 1; i < size(bottom); i++) {

10 const int c = bottom[i - 1] - 'A', n = bottom[i] - 'A';

11 for (const char c : next[c][n]) {

12 if (prev.empty()) {

13 crnt.push_back(string(1, c));

14 continue;

15 }

16 for (const auto &s : prev) {

17 if (next[s.back() - 'A'][c - 'A'].empty()) continue;

18 crnt.push_back(s + c);

19 }

20 }

21 if (crnt.empty()) return false;

22

23 prev = crnt;

24 crnt.clear();

25 }

26

27 bool res = false;

28 for (const auto &s : prev) {

29 if (!rec(s)) continue;

30 res = true;

31 break;

32 }

33 return seen[bottom] = res;

34 }

35

36 public:

37 bool pyramidTransition(const string &bottom, const vector<string> &allowed) {

38 for (const auto &s : allowed)

39 next[s[0] - 'A'][s[1] - 'A'].push_back(s[2]);

40 return rec(bottom);

41 }

42 };