756. Pyramid Transition Matrix

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string.

We are allowed to place any color block C on top of two adjacent blocks of colors A and B, if and only if ABC 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 = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  G   E
 / \ / \
B   C   D

We are allowed to place G on top of B and C because BCG is an allowed triple.  Similarly, we can place E on top of C and D, then A on top of G and E.

Example 2:

Input: bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
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:

1. bottom will be a string with length in range [2, 8].

2. allowed will have length in range [0, 200].

3. Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.

// Backtracking
bool helper(const string& cur, string above, unordered_map<string, unordered_set<char> >& mp) {
    if (cur.length() == 2 && above.length() == 1) return true;
    if (cur.length() - 1 == above.length()) return helper(above, "", mp);
    int pos = above.length();
    const string& base = cur.substr(pos, 2);
    for (const char& ch : mp[base]) {
        if (helper(cur, above + string(1, ch), mp)) return true;
    }
    return false;
}
bool pyramidTransition(string bottom, vector<string>& allowed) { // time: O(7^( (bottom_len - 1)! ) ); space: O(bottom_len - 1) + O(# of blocks in allowed)
    unordered_map<string, unordered_set<char> > mp;
    for (const string& str : allowed) mp[str.substr(0, 2)].insert(str[2]);
    return helper(bottom, "", mp);
}

// Iteration DP
bool pyramidTransition(string bottom, vector<string>& allowed) { // time: O(n^2); space: O(n^2); n: bottom length
    int n = bottom.size();
    vector<vector<vector<bool> > > dp(n, vector<vector<bool> >(n, vector<bool>(7, false) ) );
    unordered_map<char, unordered_set<string> > mp;
    for (const string& str : allowed) mp[str[2]].insert(str.substr(0, 2));
    for (int i = 0; i < n; ++i) dp[n - 1][i][bottom[i] - 'A'] = true;
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            for (char ch = 'A'; ch <= 'G'; ++ch) {
                if (!mp.count(ch)) continue;
                for (const string& str : mp[ch]) {
                    if (dp[i + 1][j][str[0] - 'A'] && dp[i + 1][j + 1][str[1] - 'A']) 
                        dp[i][j][ch - 'A'] = true;
                }
            }
        }
    }
    for (int i = 0; i < 7; ++i) {
        if (dp[0][0][i]) return true;
    }
    return false;
}