Skip to content

756. Pyramid Transition Matrix

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  bool pyramidTransition(string bottom, vector<string>& allowed) {
    unordered_map<string, vector<char>> prefixToBlocks;

    for (const string& a : allowed)
      prefixToBlocks[a.substr(0, 2)].push_back(a[2]);

    return dfs(bottom, "", 0, prefixToBlocks);
  }

 private:
  bool dfs(const string& row, const string& nextRow, int i,
           const unordered_map<string, vector<char>>& prefixToBlocks) {
    if (row.length() == 1)
      return true;
    if (nextRow.length() + 1 == row.length())
      return dfs(nextRow, "", 0, prefixToBlocks);

    const string& prefix = row.substr(i, 2);

    if (const auto it = prefixToBlocks.find(prefix);
        it != prefixToBlocks.cend())
      for (const char c : it->second)
        if (dfs(row, nextRow + c, i + 1, prefixToBlocks))
          return true;

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public boolean pyramidTransition(String bottom, List<String> allowed) {
    Map<String, List<Character>> prefixToBlocks = new HashMap<>();

    for (final String a : allowed) {
      final String lowerBlocks = a.substring(0, 2);
      prefixToBlocks.putIfAbsent(lowerBlocks, new LinkedList<>());
      prefixToBlocks.get(lowerBlocks).add(a.charAt(2));
    }

    return dfs(bottom, "", 0, prefixToBlocks);
  }

  private boolean dfs(final String row, final String nextRow, int i,
                      Map<String, List<Character>> prefixToBlocks) {
    if (row.length() == 1)
      return true;
    if (nextRow.length() + 1 == row.length())
      return dfs(nextRow, "", 0, prefixToBlocks);

    final String prefix = row.substring(i, i + 2);

    if (prefixToBlocks.containsKey(prefix))
      for (final char c : prefixToBlocks.get(prefix))
        if (dfs(row, nextRow + c, i + 1, prefixToBlocks))
          return true;

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def pyramidTransition(self, bottom: str, allowed: list[str]) -> bool:
    prefixToBlocks = collections.defaultdict(list)

    for a in allowed:
      prefixToBlocks[a[:2]].append(a[2])

    def dfs(row: str, nextRow: str, i: int) -> bool:
      if len(row) == 1:
        return True
      if len(nextRow) + 1 == len(row):
        return dfs(nextRow, '', 0)

      for c in prefixToBlocks[row[i:i + 2]]:
        if dfs(row, nextRow + c, i + 1):
          return True

      return False

    return dfs(bottom, '', 0)