LeetCode - Multiply Strings

Problem description

description

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:

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

Analysis

Just use add and multiple can get the result.

Here’s the code:

public class MultiplyStrings {
  public String multiply(String num1, String num2) {
    String res ="0";

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

    String suffix = "";
    for (int i = num1.length() - 1; i  >= 0; i--) {
      char c = num1.charAt(i);
      String a = multiple(num2, c) + suffix;
      String n = add(res, a);
      res = n;

      suffix += "0";
    }

    return res;
  }

  String add(String num1, String num2) {
    int l1 = num1.length();
    int l2 = num2.length();

    int len = Math.max(l1, l2) + 1;

    char[] res = new char[len];
    int pre = 0;

    l1--;
    l2--;

    int index = 0;

    while (l1 >= 0 || l2 >= 0) {
      int v1 = l1 >= 0 ? Character.getNumericValue(num1.charAt(l1)) : 0;
      int v2 = l2 >= 0 ? Character.getNumericValue(num2.charAt(l2)) : 0;

      int temp = v1 + v2 + pre;
      res[len - 1 - index] = (char) (temp % 10 + '0');
      pre = temp / 10;

      index++;
      l1--;
      l2--;
    }

    if (pre != 0){
      res[0] = '1';
      return new String(res);
    }

    return new String(res).substring(1);
  }

  String multiple(String num, char factor) {
    char[] n = num.toCharArray();
    int m = Character.getNumericValue(factor);

    char[] res = new char[n.length + 1];

    int pre = 0;
    for (int i = n.length - 1; i >= 0; i--) {
      int temp = m * Character.getNumericValue(n[i]) + pre;

      res[i + 1] = (char) (temp % 10 + '0');
      pre = temp / 10;
    }

    if (pre != 0) {
      res[0] = (char) (pre + '0');
      return new String(res);
    }

    return new String(res).substring(1);
  }
}

However, this solution is quite slow, there is another solution from LeetCode which is much faster.

Here’s the code:

class Solution {
    public String multiply(String num1, String num2) {
        int len1=num1.length();
        int len2 = num2.length();
        int res [] = new int [len1+len2];
        for(int i=len1-1;i>=0;i--){
           for(int j=len2-1;j>=0;j--){
              int p = (num1.charAt(i) -'0')*(num2.charAt(j)-'0') + res[i+j+1];
               res[i+j]+=p/10;
               res[i+j+1]=p%10;
           }
        }
        int index =0;
        String s ="";
        StringBuilder sb = new StringBuilder();
        while(index<res.length && res[index]==0){
            index++;
        }
       for(int i=index;i<res.length;i++){
           sb.append(res[i]);
       }
        return sb.length()==0 ? "0" : sb.toString();
    }
}

The basic idea is to use an array and do the same thing as first solution, the improvement is that it reduce the time to transfer from String to char and calculate.

What to improve

• remember to use char array to reduce the time.