【leetcode】756. Pyramid Transition Matrix

题目如下：

解题思路：我的方法是采用DFS，对于判断是否的题目，用DFS的效率要高于BFS。题目中有一点好像没有说明，就是allowed里面的同一个元素可以用多次。遍历allowed，先找出前两个字符与bottom前两个字符相同的元素；然后bottom去掉第一位，再去allowed中找出前两个字符与bottom前两个字符相同的元素，循环直至bottom长度变成1为止；接下来令bottom等于第一轮中找到的所有的元素的最后一个字符拼接组成的新的字符串，重复第一轮的操作。同时每找到一个可以组成bottom的元素，用一个变量used记录个数，直到userd =  len(bottom) * (len(bottom) -1 )/2 表示可以组成如题目要求的bottom。为什么？因为要组成三角形所需的元素个数正好等于 (1+2+3....+最底部bottom的长度)。

代码如下：

class Solution(object):

    def pyramidTransition(self, bottom, allowed):

        """

        :type bottom: str

        :type allowed: List[str]

        :rtype: bool

        """

        queue = []

        dic = {}

        for i in allowed:

            if bottom[:2] == i[:2]:

                queue.append((bottom[1:],i[-1],1))

            if i[:2] not in dic:

                dic[i[:2]] = [i]

            else:

                dic[i[:2]].append(i)

        while len(queue) > 0:

            #print len(queue)

            bot,path,used = queue.pop(0)

            #print used

            if used == len(bottom) * (len(bottom) -1 )/2:

                return True

            elif len(bot) < 2:

                queue.insert(0,(path,'',used+1))

            else:

                if bot[:2] in dic:

                    for i in dic[bot[:2]]:

                        queue.insert(0,(bot[1:], path + i[-1], used + 1))

        return False