43. 字符串相乘

本题来自 LeetCode：43. 字符串相乘^[1]

题目描述

给定两个以字符串形式表示的非负整数  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）或直接将输入转换为整数来处理。

题目分析

该题需要实现两个字符串数的的乘法，先来看下小学知识乘法的运算规则。 123 为被乘数， 456为乘数。

                        1 2 3
             X         4 5 6
                -----------
                        7    3    8            （6 * 123）* 1
             +    6    1 5 0            （5 * 123）* 10，要进位，相当于尾部要补一位0
             ------------
                6 8 8 8            (738 + 6150)
            + 4    9    2    0    0            (4 * 123) * 100，要进位，相当于尾部要补二位0
       ------------
           5    6    0    8    8            (6888 + 49200)

从上面的可以发现，乘法就是 乘数的每一位（需要进位）分别和被乘数相乘，最后类加而成的。

题目解答

解法一

class Solution {
    public String multiply(String num1, String num2) {
        if("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        String s = "0";
        String suffix = ""; // 进位尾部补0
        for(int j = num2.length() -1; j = 0; j --) {
            // 获取乘数的当前位数字
            int digit = getDigit(num2, j);
            // 用 乘数的当前位数字
            String num = digit ==  0 ? "0" : multiply(num1, digit) + suffix;
            s = add(s, num);
            suffix += "0";
        }
        return s;
    }

    // num1和一位数相乘
    public String multiply(String num1, int digit) {
        if(digit == 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = num1.length() - 1;
        while(carry != 0 || i = 0) {
            int digit1 = i = 0 ? getDigit(num1, i --) : 0;
            carry += digit1 * digit;
            sb.append(carry % 10);
            carry /= 10;
        }
        // 反转返回
        return sb.reverse().toString();
    }

    // 两数相加
    public String add(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        while(carry != 0 || i = 0 || j = 0) {
            int digit1 = i = 0 ? getDigit(num1, i --) : 0;
            int digit2 = j = 0 ? getDigit(num2, j --) : 0;
            carry += digit1 + digit2;
            sb.append(carry % 10);
            carry /= 10;
        }
        // 反转返回
        return sb.reverse().toString();
    }
    // 获取字符串num的第index位数字
    public int getDigit(String num, int index) {
        return num.charAt(index) - '0';
    }
}

复杂度分析：
时间复杂度： O(m * n)， m, n分别为 num1、 num2的长度
空间复杂度： O(m + n)， 缓存结果

解法二

从上面观察到，乘数的每位数字都要去乘以被乘数，这些结果可能会重复，故可以将被乘数 0-9倍的结果缓存起来，这样就不需要每次去计算了。

class Solution {
    public String multiply(String num1, String num2) {
        if("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }

        MapInteger, String timesCache = new HashMap();
        timesCache.put(0, "0");
        // 缓存被乘数num1的0...9倍值
        for(int i = 1; i  10; i ++) {
            timesCache.put(i, add(timesCache.get(i - 1), num1));
        }
        String s = "0";
        String suffix = "";
        for(int j = num2.length() -1; j = 0; j --) {
            int digit2 = getDigit(num2, j);
            s = add(s, timesCache.get(digit2) + suffix);
            suffix += "0";
        }
        return s;
    }

    // 两数相加
    public String add(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        while(carry != 0 || i = 0 || j = 0) {
            int digit1 = i = 0 ? getDigit(num1, i --) : 0;
            int digit2 = j = 0 ? getDigit(num2, j --) : 0;
            carry += digit1 + digit2;
            sb.append(carry % 10);
            carry /= 10;
        }
        // 反转返回
        return sb.reverse().toString();
    }
    // 获取字符串num的第index位数字
    public int getDigit(String num, int index) {
        return num.charAt(index) - '0';
    }
}

参考资料

43. 字符串相乘: https://leetcode-cn.com/problems/multiply-strings/

原文始发于微信公众号（xiaogan的技术博客）：