字符串相乘

难度：中等

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例1

输入：num1 = "2", num2 = "3" 输出："6"

示例2

输入：num1 = "123", num2 = "456" 输出：“56088”

题解

创建一个字符串构造器 $sum$，内部初始值为'0'，长度为 $num1$ 和 $num2$的和，对两个字符串从右到左遍历。

对 $sum$的第 $i+j+1$ 的位置赋值：

• 定义一个 next=sum[i+j+1]-'0'+(num1[i]-'0')*(num2[j]-'0')，因为两个字符串内的单个元素为 $char$，所以需要减去一个'0'来讲他转换为 $int$ 类型
• 将 next\%10+'0' 的值转换为 $char$ 类型之后将结果存入到 $sum[i+j+1]$

对 $sum$的第 $i+j$的位置进行赋值

• 将 $next/10$的值转换为 $char$ 类型之后将结果存入到 $sum[i+j]$ 中

最后定义一个字符串res，将sum从头删除为'0'的元素之后转换为字符串 如果res的长度为0，那么直接返回"0"，否则直接返回res

想法代码

using System.Text;

class Solution
{
    public static void Main(String[] args)
    {
        string num1 = "123456789";
        string num2 = "987654321";
        Solution solution = new Solution();
        string res = solution.Multiply(num1, num2);
        Console.WriteLine(res);
    }

    public string Multiply(string num1, string num2)
    {
        StringBuilder sum = new StringBuilder(new string('0', num1.Length + num2.Length));
        for (int i = num1.Length - 1; i >= 0; i--)
        {
            for (int j = num2.Length - 1; j >= 0; j--)
            {
                int next = sum[i + j + 1] - '0' + (num1[i] - '0') * (num2[j] - '0');
                sum[i + j + 1] = (char)(next % 10 + '0');
                sum[i + j] += (char)(next / 10);
            }
        }
        string res = sum.ToString().TrimStart('0');
        return res.Length == 0 ? "0" : res;
    }
}