You are given two sparse integer matrices A and B.
Return the matrix product A * B.
A sparse matrix contains many zero values, so your solution should avoid unnecessary multiplication involving zero values whenever possible.
You may assume that the number of columns in matrix A is equal to the number of rows in matrix B.
To keep the input simple, each matrix is represented as a List<String>. Each string represents one row of the matrix, and values inside a row are separated by commas.
The returned matrix must also be represented as a List<String>, where each string is one row of the result matrix and values inside a row are separated by commas.
Method Signature
List<String> multiplySparseMatrices(List<String> matrixA, List<String> matrixB)
Parameters
matrixA: A List<String> representing matrix A.matrixB: A List<String> representing matrix B.- Each string represents one row, for example
"1,0,3".
- Values inside each row are comma-separated integers.
Returns
- Return a
List<String> representing the matrix product A * B.
- Each returned string represents one row of the product matrix.
- Values inside each returned row must be separated by commas.
Matrix Multiplication Rule
If matrix A has size m x n and matrix B has size n x p, then the result matrix has size m x p.
Each result cell is computed as:
result[i][j] = A[i][0] * B[0][j] + A[i][1] * B[1][j] + ... + A[i][n - 1] * B[n - 1][j]
Constraints
1 ≤ matrixA.size() ≤ 1,0001 ≤ number of columns in matrixA ≤ 1,0001 ≤ matrixB.size() ≤ 1,0001 ≤ number of columns in matrixB ≤ 1,000number of columns in matrixA = matrixB.size()-1,000,000 ≤ matrix value ≤ 1,000,000- Each row string in
matrixA and matrixB contains valid comma-separated integers.
- All rows in
matrixA have the same number of values.
- All rows in
matrixB have the same number of values.
- You must never use
null as a parameter value.
Examples
Example 1
multiplySparseMatrices(matrixA = ["2,0,0", "0,0,5"], matrixB = ["3,0", "0,4", "0,6"])
Output:
["6,0", "0,30"]
Explanation:
The first row of A contributes only through value 2, and the second row contributes only through value 5.
Example 2
multiplySparseMatrices(matrixA = ["1,0,2", "-2,3,0"], matrixB = ["4,0", "0,5", "7,0"])
Output:
["18,0", "-8,15"]
Explanation:
First row result is [1 * 4 + 0 * 0 + 2 * 7, 1 * 0 + 0 * 5 + 2 * 0] = [18,0].
Second row result is [-2 * 4 + 3 * 0 + 0 * 7, -2 * 0 + 3 * 5 + 0 * 0] = [-8,15].
Example 3
multiplySparseMatrices(matrixA = ["0,0", "0,0"], matrixB = ["5,6,7", "8,9,10"])
Output:
["0,0,0", "0,0,0"]
Explanation:
Since all values in A are zero, every value in the product matrix is zero.
Example 4
multiplySparseMatrices(matrixA = ["1,2", "3,4"], matrixB = ["1,0", "0,1"])
Output:
["1,2", "3,4"]
Explanation:
Matrix B is the identity matrix, so multiplying A by B returns A.