思路

题目分析

题目给出了两个数字字符串
这两个字符串代表的数字要进行相乘操作，大数相乘可能会突破一些语言的数值表示的限制
因此我们要通过一些数据结构的表示来最终返回其两数字相乘结果，以字符串形式返回最终数字

方法一：python语言中对数字长度无要求
- 因此我们只需要将其转换成数字并相乘，最终返回字符串格式即可
方法二：乘法拆解为加法
- 我们可以将两个大数乘法拆解成竖式运算的概念
- 让一个大数分别乘另一个大数的每一位，并适当错开位数补0后进行加和

方法一：python语言中对数字位数无要求

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param s string字符串 第一个整数
# @param t string字符串 第二个整数
# @return string字符串
#
class Solution:
    def solve(self , s , t ):
        # write code here
        return str(int(s)*int(t))		# 直接转换成数字并相乘即可

复杂度分析

时间复杂度： $O(n^{log_2{3}})$ ，n为数字的位数，python内部实现以Karatsuba算法实现，该算法的时间复杂度为 $O(n^{log_2{3}})$
空间复杂度： $O(log_2{(n)})$ ，空间代价与位数有关

方法二：乘法拆解成加法

alt

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param s string字符串 第一个整数
# @param t string字符串 第二个整数
# @return string字符串
#
class Solution:
    def solve(self , s , t ):
        # write code here
        if s == "0" or t == "0":             # 特殊情况判断
            return "0"
        
        ans = "0"                            # 将乘法转换成子项的加法的累加阶段使用的变量
        m, n = len(s), len(t)                # 获得两段字符串的长度
        for i in range(n-1, -1, -1):         # 倒着遍历字符串t
            add = 0                          # 进位标识
            y = int(t[i])                    # 倒序取出字符串t的一个字符并转换成数字
            cur = ["0"] * (n - i - 1)        # 本轮次的补0个数
            for j in range(m-1, -1, -1):     # 倒着遍历字符串s
                x = int(s[j])                # 倒序取出字符串s的一个字符并转换成数字
                digit = x * y + add          # 两位相乘
                cur.append(str(digit % 10))  # 取出余数放在cur中
                add = digit // 10            # 标志是否进位
            if add > 0:                      # 判断是否最后仍需补位
                cur.append(str(add))
            cur = "".join(cur[::-1])         # 将cur中的元素倒序重新组成完整字符串
            ans = self.addStrings(ans, cur)  # 将乘法转换为加法的每一项调用addStrings进行字符串加和
        return ans                           # 返回最终结果
    
    def addStrings(self, s, t):              # 将两个字符串大数加和
        i, j = len(s) - 1, len(t) - 1        # 获取两个字符串长度
        add = 0                              # 标志进位
        ans = list()                         # 存储结果
        while i >= 0 or j >= 0 or add != 0:  # 判断两个字符串是否遍历完，并且是否仍需进位
            x = int(s[i]) if i >= 0 else 0   # 对s字符串取值或者无值后标记为0
            y = int(t[j]) if j >= 0 else 0   # 对t字符串取值或者无值后标记为0
            result = x + y + add             # 进行逐位加法
            ans.append(str(result % 10))     # 将余数作为一个加和后的数字存储在ans中
            add = result // 10               # 更新是否进位
            i -= 1
            j -= 1
        return "".join(ans[::-1])            # 最终倒序将数字重新组织成加和后的字符串

复杂度分析

时间复杂度： $O (m n + n^{2})$ ，其中m是s的长度，n是t的长度，s的每一位都要和t的每一位进行乘积共有 $m n$ 次，而字符串相加的结果最长为m+n，而一共要进行n轮，因此代价是 $m n + n^{2}$ ，整体的时间代价为 $O (2 m n + n^{2})$ 即 $O (m n + n^{2})$
空间复杂度： $O (m + n)$ ，存储字符串所借用的空间

题解 | #大数乘法#

思路

方法一：python语言中对数字位数无要求

复杂度分析

方法二：乘法拆解成加法

复杂度分析