# We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like `'Z'`.
#
# For every block of color `C` we place not in the bottom row, we are placing it on top of a left block of color `A`
# and right block of color `B`. We are allowed to place the block there only if `(A, B, C)` is an allowed triple.
#
# We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples
# allowed. Each allowed triple is represented as a string of length 3.
#
# Return true if we can build the pyramid all the way to the top, otherwise false.
#
# Example 1:
# Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
# Output: true
# Explanation:
# We can stack the pyramid like this:
#     A
#    / \
#   D   E
#  / \ / \
# X   Y   Z
#
# This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.
# Example 2:
# Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
# Output: false
# Explanation:
# We can't stack the pyramid to the top.
# Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.
# Note:
# bottom will be a string with length in range [2, 8].
# allowed will have length in range [0, 200].
# Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.
import collections


class Solution(object):
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool
        """
        m = collections.defaultdict(list)
        for a in allowed:
            m[a[:2]].append(a[2:])

        return self.backtrack(bottom, m)

    def backtrack(self, bottom, m):
        if len(bottom) == 1:
            return True

        tmp, res = [], []
        self.getBottoms(bottom, 0, m, tmp, res)

        for s in res:
            if len(s) + 1 != len(bottom):
                return False

            if self.backtrack(s, m):
                return True

        return False

    def getBottoms(self, bottom, start, m, tmp, res):
        if start + 1 >= len(bottom):
            res.append("".join(tmp))
            return

        key = bottom[start:start + 2]
        if key not in m:
            return

        choices = m[bottom[start:start + 2]]

        for c in choices:
            str = list(tmp)
            str += c,
            self.getBottoms(bottom, start + 1, m, str, res)

        return


if __name__ == '__main__':
    print Solution().pyramidTransition("XYZ", ["XYD", "YZE", "DEA", "FFF"])
    print Solution().pyramidTransition("XXYX", ["XXX", "XXY", "XYX", "XYY", "YXZ"])
