1
class Solution {
2
  HashMap<String, List<Character>> map = new HashMap<>();
3
  HashMap<String, Boolean> dp = new HashMap<>();
4

5
  public boolean pyramidTransition(String bottom, List<String> allowed) {
6
    for (String s : allowed) {
7
      String sub = s.substring(0, 2);
8

9
      char c = s.charAt(2);
10

11
      if (!map.containsKey(sub)) map.put(sub, new ArrayList<>());
12

13
      map.get(sub).add(c);
14
    }
15

16
    return dfs(bottom, "", 0);
17
  }
18

19
  boolean dfs(String currBottom, String newBottom, int index) {
20

21
    if (currBottom.length() == 1) return true;
22
    if (index + 1 >= currBottom.length()) return false;
23

24
    String sub = currBottom.substring(index, index + 2);
25

26
    String state = currBottom + " " + newBottom + " " + index;
27

28
    if (dp.containsKey(state)) return dp.get(state);
29

30
    if (map.containsKey(sub)) {
31
      List<Character> letters = map.get(sub);
32

33
      for (char c : letters) {
34
        if (index == currBottom.length() - 2) {
35
          if (dfs(newBottom + c, "", 0)) {
36
            dp.put(state, true);
37
            return true;
38
          }
39
        } else if (dfs(currBottom, newBottom + c, index + 1)) {
40
          dp.put(state, true);
41
          return true;
42
        }
43
      }
44
    }
45

46
    dp.put(state, false);
47
    return false;
48
  }
49
}