Letcode43: string multiplication

Preface ：

• Data collected by bloggers New Young, In the serial .
• Questions included by bloggers :New Young
• Reprint please indicate the source ：New Young

subject

letcode:https://leetcode.cn/problems/multiply-strings/description/

Ideas

Code

// Ideas ：
// Store the result of each multiplication in the array 
// And 

void reverseString(string& s) {
    
    size_t i = 0;
    size_t j = s.size() - 1;
    for (; i < j; ++i, --j)
    {
    
        std::swap(s[i], s[j]);
    }
}
void Sum(int* arr, int begin, const string& num, const char& ch)
{
    
    // As a result, it is impossible to fill the array , This is an invisible explanation 
    // Because the starting data header of each array is different , So use begin Let's start 
    int gap = 0;// Carry device  
    int len = num.size();
    int i = 0;
    int j = len - 1;
    while (i < len && j >= 0)
    {
    
        int sum = (num[j] - '0') * (ch - '0') + gap;
        gap = sum / 10;
        arr[begin - i] = sum % 10;
        ++i;
        --j;
    }
    if (gap != 0)// The number of result digits is greater than len
    {
    
        arr[begin - i] = gap;
        ++i;
    }
}
class Solution {
    
public:
    string multiply(string num1, string num2) {
    
        if ((strcmp(num1.c_str(), "0") == 0)
            || (strcmp(num2.c_str(), "0") == 0))
        {
    
            string s = "0";
            return s;
        }
        size_t len1 = num1.size();
        size_t len2 = num2.size();
        size_t len = len1 + len2;
        size_t min = len1;
        if (len1 > len2)
        {
    
            min = len2;
        }

        // The number of arrays depends on the shortest length string 
        int** arr = new int* [min];
        // The number of digits of the result of multiplying multiple numbers cannot be greater than the sum of digits of each number , Therefore, the length of each array is len1+len2;
        for (size_t i = 0; i < min; ++i)
        {
    
            arr[i] = new int[len];
            memset(arr[i], 0, sizeof(int) * (len));// The initialization space is 0
        }
        if (min == len2)
        {
    
            for (size_t i = 0; i < min; ++i)
            {
    
                Sum(arr[i], len - 1 - i, num1, num2[len2 -1- i]);
            }
        }
        else
        {
    
            for (size_t i = 0; i < min; ++i)
            {
    
                Sum(arr[i], len - 1 - i, num2, num1[len1 - 1 - i]);
            }

        }
        int gap = 0;// Carry device 
        int* tmp = new int[len];
        memset(tmp, 0, sizeof(int) * (len));
        for (int i = len - 1; i >= 0; --i)
        {
    
            int sum = gap;
            for (int j = 0; j < min; ++j)
            {
    
                sum += arr[j][i];
            }
            gap = sum / 10;
            tmp[i] = sum % 10;
        }
        int i = 0;
        string s;
        while (i < len)
        {
    
            if (tmp[i] != 0)
            {
    
                for (int j = i; j < len; ++j)
                {
    
                    s += tmp[j] + '0';
                }
                break;
            }
            ++i;
        }

        return s;
    }
};