PyramidTransitionMatrix_recursive , C++ (gcc)

PyramidTransitionMatrix_recursive

/* 25 String Pyramids Transition Matrix
-- leetcode 756
Given a list of leaf nodes in a pyramid, and a map which indicates what's the possible parent node given a left and right node. 
Return true if the one of leaf node could turn into the root node, Otherwise, return false. For example:

root
     / \
    X   X
   /\  /\
   X  X  X
  / \/ \/ \
 A   B  C  D
Map:

left: A |  B   |   C | D
right---------------------------------
A             B |A or C|   D | A
B             D |B or C|   A |
C                              B
D
Note:1. If left child is B, right child is A, the parent node could be B or C
Given leaf input of "ABCD", output true.

#include <vector>
#include <iostream> 
#include <map> 
#include <set> 
#include <assert.h>
using namespace std;

class Pyramid{
    map<string, set<char>> m; // all potential mapping string to a char, 
    set<char> search(string bottom) {
        if(m.count(bottom)) return m[bottom];
        int n = bottom.size();
        if(n ==2) return {}; // should return result 
        
        string s1 = bottom.substr(0,n-1);
        string s2 = bottom.substr(1); 
        set<char> r1 = search(s1); 
        set<char> r2 = search(s2); 
        
        set<char> res;
        for(char x: r1){
            for(char y: r2) {
                string xy = "xy";
                xy[0] = x; 
                xy[1] = y;
                set<char> r3 = search(xy);
                res.insert(r3.begin(), r3.end());     
            }
        }
        if(res.size())
            m[bottom] = res; 
        return res;
    }
    
public: 
    Pyramid(vector<string>& lines){
        for(auto s: lines){
            string rest = s.substr(2); 
            for(char c: rest)
                m[s.substr(0,2)].insert(c);
        }
        //cout<< "map.size() = " << m.size() << endl;
    }
    bool check(string bottom){
        if(bottom.size()<2) return false;
        set<char> res = search(bottom);
        //cout << "res.size=" << res.size() << endl;
        return res.size()>0; 
    }
};
int main(){
    vector<string> lines = {"AAAC", "ABCD", "ACD", "ADB",
                    "BAB", "BBC", "BCA", "BDCD",
                    "CAA", "CBC", "CCD", "CDB",
                    "DABC", "DBD", "DCA", "DDC"}; 
    Pyramid p(lines);
    string bottom = "AACD";
    bool res = p.check(bottom); 
    cout << ( res==true? "True" : "False") << endl;
    
    assert(p.check("ABCD"));
    assert(p.check("AACD"));
    assert(p.check("AAAA"));
    assert(p.check("CCCC"));
    assert(p.check("DDDD"));
    
    return 0; 
}


run \| edit \| history \| help	0