My Python 11/12 tests passed solution


  • 0
    D
    class Solution(object):
        
        # O(n^3). This approach is correct but timeout 11/12 test cases passed.
        def multiply(self, A, B):
            """
            :type A: List[List[int]]
            :type B: List[List[int]]
            :rtype: List[List[int]]
            """
            rowsA, colsA = len(A), len(A[0])
            rowsB, colsB = len(B), len(B[0])
            C   = [[0 for i in range(rowsB)] for j in range(colsB)]
            ret = [[0 for i in range(colsB)] for j in range(rowsA)]
            index = 0
            
            # reposition the B into C. Switch rows and cols!
            for col in range(colsB):
                for row in range(rowsB):
                    C[col][row] = B[row][col]
            
            # print(C)
            for row in range(rowsA):
                for col in range(colsB):
                    temp = 0
                    for rowB in range(rowsB):
                        temp += C[col][rowB] * A[row][rowB]
                    ret[row][col] = temp
            
            return self.multiply2(A,B)
        
        
        def multiply2(self, A, B):
            """
            :type A: List[List[int]]
            :type B: List[List[int]]
            :rtype: List[List[int]]
            """
            rowsA, colsA = len(A), len(A[0])
            rowsB, colsB = len(B), len(B[0])
            ret = [[0 for i in range(colsB)] for j in range(rowsA)]
            index = 0
            
            for row in range(rowsA):
                for col in range(colsA):
                    if A[row][col] != 0:
                        rowB = col
                        for colB in range(colsB):
                            if B[rowB][colB] != 0:
                                ret[row][colB] += A[row][col] * B[rowB][colB]
            
            return ret
                    
                    
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.