43. 字符串相乘：

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

样例 1：

输入: 
num1 = "2", num2 = "3"

输出: 
"6"
1
2
3
4
5

样例 2：

输入: 
num1 = "123", num2 = "456"

输出: 
"56088"
1
2
3
4
5

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 看了题意就是不允许我们直接将输入的两个数转成数字，然后直接用乘法API，那我们就模拟大数乘法就可以了。
• 想起了小学做数学乘法，先学9*9乘法表，之后的乘法都是“分治”为个位数的乘法，再把结果加起来。

题解：

rust

impl Solution {
    pub fn multiply(num1: String, num2: String) -> String {
        if num1 == "0" || num2 == "0" {
            return "0".to_owned();
        }
        let (m, n) = (num1.len(), num2.len());
        let mut ans_arr = vec![0; m + n - 1];
        num1.as_bytes().iter().enumerate().for_each(|(i1, &c1)| {
            num2.as_bytes().iter().enumerate().for_each(|(i2, &c2)| {
                ans_arr[i1 + i2] += ((c1 - b'0') * (c2 - b'0')) as u16;
            });
        });
        let mut carry = 0;
        let mut ans = Vec::with_capacity(m + n);
        ans_arr.iter().rev().for_each(|&c| {
            let mut b = c + carry;
            carry = b / 10;
            b %= 10;
            ans.push(b as u8 + b'0');
        });
        if carry > 0 {
            ans.push(carry as u8 + b'0');
        }
        ans.reverse();
        String::from_utf8(ans).unwrap()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

go

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
return "0"
}
m, n := len(num1), len(num2)
ansArr := make([]int, m+n)
for i1, c1 := range num1 {
for i2, c2 := range num2 {
ansArr[i1+i2+1] += int(c1-'0') * int(c2-'0')
}
}
for i := m + n - 1; i > 0; i-- {
ansArr[i-1] += ansArr[i] / 10
ansArr[i] %= 10
}
ans := ""
idx := 0
if ansArr[0] == 0 {
idx = 1
}
for ; idx < m+n; idx++ {
ans += strconv.Itoa(ansArr[idx])
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

c++

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int m = num1.size(), n = num2.size();
        auto ansArr = vector<int>(m + n);
        for (int i = m - 1; i >= 0; --i) {
            int x = num1.at(i) - '0';
            for (int j = n - 1; j >= 0; --j) {
                int y = num2.at(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; --i) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        string ans;
        while (index < m + n) {
            ans.push_back(ansArr[index] + '0');
            index++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

c

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));
    if ((m == 1 && num1[0] == '0') || (n == 1 && num2[0] == '0')) {
        ans[0] = '0', ans[1] = 0;
        return ans;
    }
    int *ansArr = malloc(sizeof(int) * (m + n + 3));
    memset(ansArr, 0, sizeof(int) * (m + n + 3));
    for (int 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 (int i = m + n - 1; i > 0; --i) {
        ansArr[i - 1] += ansArr[i] / 10;
        ansArr[i] %= 10;
    }
    int index = ansArr[0] == 0 ? 1 : 0;
    int ansLen = 0;
    while (index < m + n) {
        ans[ansLen++] = ansArr[index] + '0';
        ++index;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

python

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"

        m, n = len(num1), len(num2)
        ans_arr = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            x = int(num1[i])
            for j in range(n - 1, -1, -1):
                ans_arr[i + j + 1] += x * int(num2[j])

        for i in range(m + n - 1, 0, -1):
            ans_arr[i - 1] += ans_arr[i] // 10
            ans_arr[i] %= 10

        index = 1 if ans_arr[0] == 0 else 0
        ans = "".join(str(x) for x in ans_arr[index:])
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

java

class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int   m      = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n - 1];
        for (int i = m - 1; i >= 0; --i) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; --j) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j] += x * y;
            }
        }
        StringBuilder ans   = new StringBuilder();
        int           carry = 0;
        for (int i = m + n - 2; i >= 0; --i) {
            int b = ansArr[i] + carry;
            carry = b / 10;
            b %= 10;
            ans.append(b);
        }
        if (carry > 0) {
            ans.append(carry);
        }
        return ans.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~