[LeetCode] Challenge log 756

Posted on | Edited on |
756. Pyramid Transition Matrix

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

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like 'Z'.

For every block of color C we place not in the bottom row, we are placing it on top of a left block of color A and right block of color B. We are allowed to place the block there only if (A, B, C) is an allowed triple.

We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.

Example 2:

1
2
3
4
5
Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
Output: false
Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.

Note:

  1. bottom will be a string with length in range [2, 8].
  2. allowed will have length in range [0, 200].
  3. Letters in all strings will be chosen from the set {'A', 'B', 'C', 'D', 'E', 'F', 'G'}.
Solution:
  • Build all possible bottoms for nect level and recur.
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
31
32
33
34
35
36
37
class Solution:
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool
        """
        hashmap = {}
        for tp in allowed:
            if tp[:2] not in hashmap:
                hashmap[tp[:2]] = [tp[2]]
            else:
                hashmap[tp[:2]].append(tp[2])
        print(hashmap)
        return self.pyramidOk(bottom, hashmap)
    
    def pyramidOk(self, bottom, hashmap):
        if len(bottom) == 1: return True
        bottomList = []
        for i in range(len(bottom)-1):
            if bottom[i:i+2] not in hashmap: 
                return False
            else:
                bottomList.append(hashmap[bottom[i:i+2]])
        newBottom = []
        self.makeBottom(bottomList, newBottom, '')
        for bt in newBottom:
            if self.pyramidOk(bt, hashmap):
                return True
        return False
        
    def makeBottom(self, bottomList, newBottom, curr):
        if len(bottomList) == 0: 
            newBottom.append(curr)
            return curr
        for i in bottomList[0]:
            self.makeBottom(bottomList[1:], newBottom, curr + i)
  • A slightly different version, use yield and iterator to save 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
31
32
33
34
35
36
37
38
class Solution:
    def pyramidTransition(self, bottom, allowed):
        """
        :type bottom: str
        :type allowed: List[str]
        :rtype: bool
        """
        hashmap = {}
        for tp in allowed:
            if tp[:2] not in hashmap:
                hashmap[tp[:2]] = [tp[2]]
            else:
                hashmap[tp[:2]].append(tp[2])
        return self.pyramidOk(bottom, hashmap)
    
    def pyramidOk(self, bottom, hashmap):
        if len(bottom) == 1: return True
        
        bottomList = []
        for i in range(len(bottom)-1):
            if bottom[i:i+2] not in hashmap: 
                return False
            else:
                bottomList.append(hashmap[bottom[i:i+2]])

        for bt in self.makeBottom(bottomList, ''): 
            if self.pyramidOk(bt, hashmap):
                return True
            
        return False
        
    def makeBottom(self, bottomList, curr):
        if len(bottomList) == 0: 
            yield curr
        else:
            for i in bottomList[0]:
                for j in self.makeBottom(bottomList[1:], curr + i):
                    yield j
0%