43. Multiply Strings (Medium)

https://leetcode.com/problems/multiply-strings/

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contain only digits 0-9.
  3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solutions

class Solution {

    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) {
            return "";
        }

        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        String sum = "0";
        for (int i = 0; i < num2.length(); i++) {
            // num2 multiplies num1 one by one digit.
            // Do not forget to append tailing 0
            String rst = singleMul(num1, num2.charAt(num2.length() - i - 1)) + appendix0(i);

            // Then sum up the result one by one digit.
            sum = add(sum, rst);
        }

        return sum;
    }

    private String appendix0(int x) {
        String ans = "";
        for (int i = 0; i < x; i++) {
            ans += "0";
        }

        return ans;
    }

    private String singleMul(String x1, char x2) {
        if (x2 == '0') {
            return "0";
        }

        if (x2 == '1') {
            return x1;
        }

        String tmp = "";

        int carry = 0;
        for (int i = 0; i < x1.length(); i++) {
            int a = x1.charAt(x1.length() - i - 1) - '0';

            int v = a * (x2 - '0') + carry;

            tmp += v % 10;

            carry = v / 10;
        }

        if (carry != 0) {
            tmp += carry;
        }

        return reverseString(tmp);
    }

    private String add(String x1, String x2) {
        int len1 = x1.length();
        int len2 = x2.length();

        int len = Math.max(len1, len2);

        String tmp = "";

        int carry = 0;
        for (int i = 0; i < len; i++) {
            int v1 = 0;
            if (i < len1) {
                v1 = x1.charAt(len1 - i - 1) - '0';
            }

            int v2 = 0;
            if (i < len2) {
                v2 = x2.charAt(len2 - i - 1) - '0';
            }

            int v = (v1 + v2 + carry) % 10;
            carry = (v1 + v2 + carry) / 10;

            tmp += v;
        }

        if (carry != 0) {
            tmp += carry;
        }

        return reverseString(tmp);
    }

    private String reverseString(String x) {
        int t;
        for (t = 0; t < x.length(); t++) {
            if (x.charAt(x.length() - t - 1) != '0') {
                break;
            }
        }

        x = x.substring(0, x.length() - t);

        String ans = "";
        for (int i = 0; i < x.length(); i++) {
            ans += x.charAt(x.length() - i - 1);
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""