C language force deduction question 43 string multiplication. Optimized vertical

Given two non negative integers in the form of strings num1 and num2, return num1 and num2 The product of the , Their product is also represented as a string .

Be careful ： You cannot use any built-in BigInteger Library or directly convert the input to an integer .

Example 1:

Input : num1 = "2", num2 = "3"
Output : "6"

Example 2:

Input : num1 = "123", num2 = "456"
Output : "56088"

Tips ：

    1 <= num1.length, num2.length <= 200
    num1 and num2 It can only consist of numbers .
    num1 and num2 It doesn't contain any leading zeros , In addition to digital 0 In itself .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/multiply-strings
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Use arrays instead of strings to store results , You can reduce the operation of strings .

Make m  and n  respectively  num1​  and  num2 The length of , And none of them is  0, be  num1 and  num2 The length of the product of is  m+n−1 or  m+n. The simple proof is as follows ：

—— If  num1​  and  num2​  Take the minimum , be  num1=10^{m-1},num2=10^{n-1},num1×num2=10^{m+n-2}, The length of the product is  m+n−1;

—— If  num1​  and  num2 Take the maximum , be  num1=10^m-1,num2=10^n-1,num1×num2=10^{m+n}-10^m-10^n+1, The product is obviously smaller than 10^{m+n} And greater than 10^{m+n-1}, So the length of the product is  m+n.

because  num1​  and  num2​  The maximum length of the product of is  m+n, Therefore, the creation length is  m+n Array of  ansArr Used to store the product . For any  0≤i<m and  0≤j<n,num1[i]×num2[j] The results are located in  ansArr[i+j+1], If  ansArr[i+j+1]≥10, Then add the carry part to  ansArr[i+j].

Last , Will array  ansArr Convert to string , If the highest level is  0 Then discard the highest position .

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

char * multiply(char * num1, char * num2)
{
	int m = strlen(num1), n = strlen(num2);
	char* ans = malloc(sizeof(char) * (m + n + 3));
	memset(ans, 0, sizeof(char) * (m + n + 3));
	int* ansArr = malloc(sizeof(int) * (m + n + 3));
	memset(ansArr, 0, sizeof(int) * (m + n + 3));
	int i = 0;
	int ansLen = 0;
	int index = 0;

	if ((m == 1 && num1[0] == '0') || (n == 1 && num2[0] == '0')) 
	{
		ans[0] = '0', ans[1] = 0;
		return ans;
	}

	for ( i = m - 1; i >= 0; i--) {
		int x = num1[i] - '0';
		for (int j = n - 1; j >= 0; j--) {
			int y = num2[j] - '0';
			ansArr[i + j + 1] += x * y;
		}
	}
	for ( i = m + n - 1; i > 0; i--) {
		ansArr[i - 1] += ansArr[i] / 10;
		ansArr[i] %= 10;
	}
	index = ansArr[0] == 0 ? 1 : 0;
	ansLen = 0;
	while (index < m + n) {
		ans[ansLen++] = ansArr[index];
		index++;
	}
	for ( i = 0; i < ansLen; i++) ans[i] += '0';
	return ans;

}

int main()
{
	char num1[] = "123";
	char num2[] = "456";
	char num3[1000] = "";
	strcpy(num3,multiply(num1, num2));
	printf("%s", num3);
	return 0;
}