题目描述

给定一个bottom字符串，和allowed数组。
其中allowed数组中每一个字符串都含有三个字符(A,B,C)
allowed数组表达一种规则，表示C的左孩子可以是A，右孩子可以是B。
写一个程序判断给定bottom和allowed，是否能构造一个金字塔的结构，满足allowed的规则，并且金字塔的最后一层就是bottom字符串。

样例

输入：bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
输出 :true
可以形成如下所示的金字塔
    A
   / \
  D   E
 / \ / \
X   Y   Z


输入：bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
不存在最底层为XXYX的字符串
输出:false

算法

(DFS) $O(2^n)$

在确定了一行的字符串以后，可以利用当前状态确定上一行，这样一直递推，可以确定最上面一层的状态。
如果最上面一层有字符出现，那么表明有存在的解，否则没有存在的解。

可以考虑从最底层开始搜索，遍历所有可能的字符串，在每一次都利用当前的bottom，标记当前扫描到的位置idx。
去allowed数组中查询是否有符合规则的字符，如果有，在当前行加上，并且进行下一轮的搜索。
如果没有就说明无法找到。

时间复杂度分析：枚举每一种情况，所以复杂度为 $O(2^n)$

C++ 代码

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {

        return dfs(bottom.size()-1,0,bottom,"",allowed);
    }
    bool dfs(int depth , int idx,string bottom,string curbottom,vector<string>& allowed){
        if (curbottom.size()==bottom.size()-1){
            if (curbottom.size()==1) return true;
            return dfs(depth-1,0,curbottom,"",allowed);
        }

        for (auto c : allowed){
            if (c[0] == bottom[idx] && c[1] == bottom[idx+1]){
                if (dfs(depth,idx+1,bottom,curbottom+c[2],allowed))
                    return true;
            }
        }
        return false;
    }

};