【字符串】43. 字符串相乘

 1 class Solution {
 2 public:
 3     string multiply(string num1, string num2) 
 4     {
 5         int m = num1.size();
 6         int n = num2.size();
 7 
 8         // 结果最多为 m + n 位数
 9         vector<int> res(m + n, 0);
10 
11         // 从个位数开始逐位相乘
12         for (int i = m - 1; i >= 0; i--)
13         {
14             for (int j = n - 1; j >= 0; j--) 
15             {
16                 int mul = (num1[i]-‘0‘) * (num2[j]-‘0‘);
17                 // 乘积在 res 对应的索引位置
18                 int p1 = i + j, p2 = i + j + 1;
19                 // 叠加到 res 上
20                 int sum = mul + res[p2];
21                 res[p2] = sum % 10;
22                 res[p1] += sum / 10;
23             }
24         }
25 
26         // 结果前缀可能存的 0（未使用的位）
27         int i = 0;
28         while (i < res.size() && res[i] == 0)
29         {
30             i++;
31         }
32         // 将计算结果转化成字符串
33         string str;
34         for (; i < res.size(); i++)
35         {
36             str.push_back(‘0‘ + res[i]);
37         }
38         
39         return str.size() == 0 ? "0" : str;
40     }
41 
42 };