LeetCode - 43. 字符串相乘

题目

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

示例 1:

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

示例 2:

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

说明：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理

解答

原理:

依据以下规则去操作字符串：

 *                                          1                        2                       3
 *                                        × 4                        5                       6
 * ----------------------------------------------------------------------------------------------------
 *                                          1 × 6 = 6                2 × 6 = 12              3 × 6 = 18
 *                      1 × 5 = 5           2 × 5 = 10               3 × 5 = 15
 * 1× 4 = 4             2 × 4 = 8           3 * 4 = 12
 * ----------------------------------------------------------------------------------------------------
 * 4                    8 + 5 = 13          6 + 10 + 12 = 28         12 + 15 = 27           18
 * （4 + 1） % 10 = 5   （13 + 3） % 10 = 6  （28 +  2） % 10 = 0      (27 + 1) % 10 = 8      18 % 10 = 8
 * ----------------------------------------------------------------------------------------------------
 * 5                    6                   0                        8                      8

实现代码：

 /**
 *  字符串相乘。
 * @param num1 ： 输入字符串1.
 * @param num2 : 输入字符串2.
 * @return : 返回两个字符串相乘的结果。
 * 如:
 * 输入 “123”，“456”
 * 返回 “56088”
 */
public String multiply(String num1, String num2) {
    //任何数乘以0得0.
    if (num1.equals("0") || num2.equals("0")) {
        return "0";
    }
    int len1 = num1.length();
    int len2 = num2.length();
    int totalLen = len1 + len2;
    int[] result = new int[totalLen];
    //从个位操作，把每一位相乘的结果放到一个数组中。
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            //char 类型的数字作运算，要作一个转换，因为 char的‘0’ 是 48,所以减去48.
            result[totalLen - 1 - (len1 - 1 - i) - (len2 - 1 - j)] += (num1.charAt(i) - 48) * (num2.charAt(j) - 48);
        }
    }

    //把每一位化成个位数的格式。
    int lastDec = 0;
    for (int i = totalLen - 1; i >= 0; i--) {
        result[i] += lastDec;
        lastDec = result[i] / 10;
        result[i] = result[i] % 10;
    }

    //去掉前面的0,把生成的数组转换成字符串形式。l
    StringBuilder sb = new StringBuilder();
    boolean validTag = false;
    for (int res : result) {
        if (res == 0 && !validTag) {
            validTag = true;
            continue;
        }
        validTag = true;
        sb.append(res);
    }

    return sb.toString();
}