Leetcode 756: Pyramid Transition Matrix

 https://leetcode.com/problems/pyramid-transition-matrix/description/

Notes:

This question can be solved by recursion. 

The first step is to convert the bottom to a next layer which has a smaller size  than the bottom layer by 1. The we have to solve the same question but with a size smaller by 1. So it is a typical recursion question.

However, when we convert the bottom to the next layer, there may be more than one possibilities. So we need to check all of them until find a valid one (only one element left).

Once a valid one is found, return true.

If we go through all the possibilities, but still do not find a valid one, return false.

See the code below:

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string, vector<char>> mp;
        for(auto &a : allowed) {
            string s = "";
            s.push_back(a[0]);
            s.push_back(a[1]);
            mp[s].push_back(a[2]);
        }
        bool find = false;
        return dfs(bottom, mp, find);
    }
private:
    bool dfs(string& bs, unordered_map<string, vector<char>>& mp, bool& find) {
        if(find || bs.size() == 1) return true;
        vector<string> ns;
        dfs1(bs, 0, "", ns, mp);
        for(auto &s : ns) {
            if(s.size() + 1 != bs.size()) return false;
            if(dfs(s, mp, find)) {
                find = true;
                return true;
            }
        }
        return false;
    }
    void dfs1(string&bs, int id, string temp, vector<string>& ns, unordered_map<string, vector<char>>& mp) {
        if(id+1== bs.size()) {
            if(temp.size() + 1 == bs.size()) ns.push_back(temp);
            return;
        }
        string s = "";
        s.push_back(bs[id]);
        s.push_back(bs[id+1]);
        if(!mp.count(s)) return;
        for(auto &c : mp[s]) {
            //temp.push_back(c);
            dfs1(bs, id+1, temp+c, ns, mp);
            //temp.pop_back();
        }
    }
};

Here is another way to code, which is much shorter (and faster, and also easy to understand...):

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string, vector<char>> mp;
        for(auto &a : allowed) mp[a.substr(0, 2)].push_back(a[2]);
        return dfs(bottom, mp, 0, "");
    }
private:
    bool dfs(string& bs, unordered_map<string, vector<char>>& mp, int id, string next) {
        if(bs.size() == 1) return true;
        if(id + 1 == bs.size()) return dfs(next, mp, 0, "");
        for(auto &a : mp[bs.substr(id, 2)]) {
            if(dfs(bs, mp, id+1, next + a)) return true;
        }
        return false;
    }
};