Leetcode 43. 字符串相乘

43. 字符串相乘

解法：利用竖式乘法原理（小学数学）

思路：这边找的是一个老哥的优化版，而且也比较好理解，写起来也不复杂。

https://leetcode-cn.com/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean/

可能有两个点需要理解下：

1. res[i+j+1]与 res[i+j]溢出问题，首先 i，j 是递减的，所以 res 数组填充是从后到前的，res[i+j+1]是取余不会存在溢出，res[i+j]是会的，但res[i+j]在下一步会变成res[i+j+1]，所以这里就被处理了。
2. 为什么最后需要过滤第一个0，这里引用评论区的一句话：m位乘以n位是m+n-1位到m+n位。

时间复杂度：O(M N)。M,N 分别为 num1 和 num2 的长度。

空间复杂度：O(M+N)。用于存储计算结果。

class Solution {
    fun multiply(num1: String, num2: String): String {
        if (num1 == "0" || num2 == "0") {
            return "0"
        }

        val c1 = num1.toCharArray()
        val c2 = num2.toCharArray()

        val res = IntArray(c1.size + c2.size) { 0 }
        for (i in c1.size - 1 downTo 0) {
            val n1 = c1[i] - '0'
            for (j in c2.size - 1 downTo 0) {
                val n2 = c2[j] - '0'
                val sum = (res[i + j + 1] + n1 * n2)
                //低位 取余
                res[i + j + 1] = sum % 10
                //高位
                res[i + j] += sum / 10
            }
        }

        val builder = StringBuilder()
        for (i in res.indices) {
            if (i == 0 && res[i] == 0) continue
            builder.append(res[i])
        }
        return builder.toString()
    }
}