String pyramids transition matrix - Airbnb

Related: LeetCode 756 - Pyramid Transition Matrix
airbnb面试题汇总
给一个满二叉树的所有叶子，比如 A B C D E F， 然后给一个map，记录了左右孩子分别给了的时候，父亲节点可能的值。例如 左 A 右 B =》 AC，意味着倒数第二层第一个节点可以是A或者是C。然后要求是给几个字母，问这个树的root节点是否可能是这几个字母之一。follow up是加速，记忆化搜索（不是很好写）。

https://discuss.leetcode.com/topic/90763/string-pyramid-transition-matrix
https://stackoverflow.com/questions/43432699/string-pyramid-transition-matrix

Problem: 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.

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

给一个满二叉树的所有叶子，比如 A B C D E F， 然后给一个map，记录了左右孩子分别给了的时候，父亲节点可能的值。例如 左 A 右 B =》 AC，意味着倒数第二层第一个节点可以是A或者是C。然后要求是给几个字母，问这个树的root节点是否可能是这几个字母之一。follow up是加速，记忆化搜索（不是很好写）。
https://github.com/allaboutjst/airbnb/blob/master/README.md
https://github.com/allaboutjst/airbnb/blob/master/src/main/java/string_pyramids_transition_matrix/StringPyramidsTransitionMatrix.java

        Map<String, Set<Character>> map;
        private Map<String, Boolean> cache;
        final String SEP = "###";

        Solution(String[] line) {
            cache = new HashMap<>();
            map = new HashMap<>();
            for (String s : line) {
                String[] splitted = s.split(",");
                String key = splitted[0] + SEP + splitted[1];
                Set<Character> set = new HashSet<>();
                for (char c : splitted[2].toCharArray())
                    set.add(c);
                map.put(key, set);
            }
        }

        private void getNextLevel(List<String> res, String curr, int start, StringBuilder sb) {
            if (start == curr.length() - 1) {
                res.add(new String(sb));
                return;
            }
            for (int i = start; i < curr.length() - 1; i++) {
                String key = curr.charAt(i) + SEP + curr.charAt(i + 1);
                for (char c : map.get(key)) {
                    sb.append(c);
                    getNextLevel(res, curr, start + 1, sb);
                    sb.setLength(sb.length() - 1);
                }
            }
        }

        private boolean search(String input, String current) {
            if (cache.containsKey(input)) return cache.get(input);
            if (current.length() == 1) {
                cache.put(current, input.contains(current));
                return cache.get(current);
            }

            List<String> cands = new ArrayList<>();
            getNextLevel(cands, current, 0, new StringBuilder());
            for (String cand : cands) {
                // System.out.println(cand);
                if (cache.containsKey(cand)) return cache.get(cand);
                boolean res = search(input, cand);
                if (res) {
                    cache.put(cand, true);
                    return true;
                }
            }

            return false;
        }

        public boolean check(String input) {
            cache.clear();
            return search(input, input);
        }
    }

def generate_status(all_status, matrix):
    if len(all_status) == 1:
        return all_status[0]

    next_all_status = []
    for i in xrange(len(all_status) - 1):
        cur_status = set()
        for first in all_status[i]:
            for second in all_status[i + 1]:
                cur_status |= set(list(matrix[first][second]))
        next_all_status.append(cur_status)

    return generate_status(next_all_status, matrix)


def is_legal_status(nodes, status, matrix):
    all_status = [set(node) for node in nodes]
    return status in generate_status(all_status, matrix)

nodes = "ABCD"
matrix = collections.defaultdict(lambda: collections.defaultdict(list))
matrix['A']['A'] = ['B']
matrix['A']['B'] = ['A', 'C']
matrix['A']['C'] = ['D']
matrix['A']['D'] = ['A']
matrix['B']['A'] = ['D']
matrix['B']['B'] = ['B', 'C']
matrix['B']['C'] = ['A']
matrix['C']['D'] = ['B']
print is_legal_status(nodes, 'D', matrix)

typedef unordered_map<char, unordered_map<char, unordered_set<char> > > matrixInfo;
void generateStatus(vector<unordered_set<char> >& allStatus, matrixInfo& matrix) {
    if (allStatus.size() == 1) return;
    const int n = allStatus.size();
    for (int i = 0; i < n - 1; ++i) {
        unordered_set<char> st;
        for (auto first : allStatus[i]) {
            for (auto second : allStatus[i + 1]) {
                st.insert(matrix[first][second].begin(), matrix[first][second].end());
            }
        }
        allStatus[i] = st;
    }
    allStatus.pop_back();
    generateStatus(allStatus, matrix);
}

bool checkStatus(matrixInfo& matrix, char result, const string status) {
    vector<unordered_set<char> > allStatus;
    for (auto c : status) {
        unordered_set<char> tmp;
        tmp.insert(c);
        allStatus.push_back(tmp);
    }
    generateStatus(allStatus, matrix);
    return allStatus[0].count(result) != 0;
}

int main() {
    matrixInfo mi;
    mi['A']['A'].insert('B');
    mi['A']['B'].insert('A');
    mi['A']['B'].insert('C');
    mi['A']['C'].insert('D');
    mi['A']['D'].insert('A');
    mi['B']['A'].insert('D');
    mi['B']['B'].insert('B');
    mi['B']['B'].insert('C');
    mi['B']['C'].insert('A');
    mi['C']['D'].insert('B');
    cout<<checkStatus(mi, 'A', "ABCD")<<endl;
}