756. Pyramid Transition Matrix

The basic idea is transiting the given input string from bottom to up level by level until we reach the summit, i.e., the length of input string is 1. We can solve the problem with hashtable and backtracking:

1. For each element s in allowed, we save the map from s[0, 2] to s[3];
2. For current input string, if it cannot transit to next level, return false. Otherwise, traverse all possible strings of next level it can transit, return true if any of its successive string can reach the summit.

public boolean pyramidTransition(String bottom, List<String> allowed) {
    Map<String, List<Character>> strToChar = new HashMap<String, List<Character>>();
    for(int i = 0; i < allowed.size(); i++) {
        strToChar.putIfAbsent(allowed.get(i).substring(0, 2), new ArrayList<Character>());
        strToChar.get(allowed.get(i).substring(0, 2)).add(allowed.get(i).charAt(2));
    }

    return help(bottom, strToChar);
}

public boolean help(String current, Map<String, List<Character>> strToChar) {
    if( current.length() == 1 )
        return true;
	
    List<List<Character>> charList = new ArrayList<List<Character>>();
    for(int i = 0; i < current.length() - 1; i++) {
        String substr = current.substring(i, i + 2);
        List<Character> currentList = strToChar.getOrDefault(substr, null);
        if( currentList == null ) {
            return false;
        }
        charList.add(currentList);
    }
	
    List<String> resultList = new ArrayList<String>();
    traverse(resultList, charList, 0, new StringBuilder(""));

    for(int i = 0; i < resultList.size(); i++) {
        if( help(resultList.get(i), strToChar) )
            return true;
    }
    return false;
}

public void traverse(List<String> resultList, List<List<Character>> charList, int index, StringBuilder sb) {
    if( index == charList.size() ) {
        resultList.add(sb.toString());
        return;
    }
    List<Character> currentList = charList.get(index);
    for(int i = 0; i < currentList.size(); i++) {
        sb.append(currentList.get(i));
        traverse(resultList, charList, index + 1, sb);
        sb.deleteCharAt(index);
    }
}