1
class Solution(object):
2
    def pyramidTransition(self, bottom, allowed):
3
        """
4
        :type bottom: str
5
        :type allowed: List[str]
6
        :rtype: bool
7
        """
8
        dic = defaultdict(list)
9
        for i in allowed:
10
            dic[(i[0], i[1])].append(i[2])
11

12
        res = []
13

14
        def dfs(arr, nxt):
15
            # base case second floor and check top exists
16
            if len(arr) == 2 and dic[(arr[0], arr[1])]:
17
                return True
18

19
            # go to the next row now
20
            if len(arr) == len(nxt) + 1:
21
                return dfs(nxt, [])
22

23
            # keep iterating the same row
24
            if dic[(arr[len(nxt)], arr[len(nxt) + 1])]:
25
                for val in dic[(arr[len(nxt)], arr[len(nxt) + 1])]:
26
                    if dfs(arr, nxt + [val]):
27
                        return True
28
            return False
29

30
        return dfs(bottom, [])