题目

43. 字符串相乘

在这里插入图片描述

方法一：模拟

竖式乘法示意图如下：

在这里插入图片描述

通过模拟「竖式乘法」的方法计算乘积，计算 $\textit{s}$ 的每一位和 $\textit{t}$ 的每一位的乘积进行存储，然后做加法。

class Solution {
    public String multiply(String s, String t) {
        if ("0".equals(s) || "0".equals(t)) {
            return "0";
        }
        int sLen = s.length(), tLen = t.length();
        // 字符串转换为数字数组，高位在低索引位置
        int[] sArr = new int[sLen];
        int[] tArr = new int[tLen];
        for (int i = 0; i < sLen; i++) {
            sArr[i] = s.charAt(i) - '0';
        }
        for (int i = 0; i < tLen; i++) {
            tArr[i] = t.charAt(i) - '0';
        }
        // 开辟结果数组，不考虑进位，结果长度为 sLen + tLen - 1
        int[] result = new int[sLen + tLen - 1];
        // 开始计算，先不考虑进位，每次结果存在result[i + j]位置
        // 结果数组计算处理高位在数组左，低位在数组右
        for (int i = 0; i < sLen; i++) {
            for (int j = 0; j < tLen; j++) {
                result[i+j] += sArr[i] * tArr[j];
            }
        }
        // 进位
        int carry = 0;
        StringBuilder res = new StringBuilder();
        int idx = result.length - 1;
        // 累加
        while ((idx >= 0) || carry != 0) {
            int sum = idx >= 0 ? carry + result[idx] : carry;
            res.append(sum % 10);
            carry = sum / 10;
            idx--;
        }

        // 如果最终res长度为0，结果应该输出“0”
        return res.length() == 0 ? "0" : res.reverse().toString();
    }
}

时间复杂度： $O (m n)$ ，其中 $m$ 和 $n$ 分别是 $\textit{s}$ 和 $\textit{t}$ 的长度。需要计算 $\textit{s}$ 的每一位和 $\textit{t}$ 的每一位的乘积
空间复杂度： $O (m + n)$ 。需要创建一个长度为 $m + n ? 1$ 的数组存储乘积