Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
The length of both num1 and num2 is < 110.Both num1 and num2 contains only digits 0-9.Both num1 and num2 does not contain any leading zero.You must not use any built-in BigInteger library or convert the inputs to integer directly.Solution1:
public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) { return "0"; } char[] result = new char[num1.length() + num2.length()]; for (int i = num1.length() - 1; i >= 0; i--) { for (int j = num2.length() - 1; j >= 0; j--) { multiply(num1.charAt(i), num2.charAt(j), result, i + j + 1); } } int index = result[0] == 0 ? 1 : 0; return new String(result, index, result.length - index); } private void plus(int i, int index, char[] chars) { if (i == 0 && index <= 0) { return; } if (chars[index] == 0) { chars[index] = (char) (i + '0'); } else { int x = (chars[index] - '0') + i; chars[index] = (char) (x % 10 + '0'); plus(x / 10, index - 1, chars); } } private void multiply(char c1, char c2, char[] chars, int index) { int x = (c1 - '0') * (c2 - '0'); plus(x % 10, index, chars); plus(x / 10, index - 1, chars); }Solution2:
public String multiply(String num1, String num2) { int m = num1.length(), n = num2.length(); int[] pos = new int[m + n]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); int p1 = i + j, p2 = i + j + 1; int sum = mul + pos[p2]; pos[p1] += sum / 10; pos[p2] = (sum) % 10; } } StringBuilder sb = new StringBuilder(); for (int p : pos) if (!(sb.length() == 0 && p == 0)) sb.append(p); return sb.length() == 0 ? "0" : sb.toString(); }Solution3:
better
public String multiply(String num1, String num2) { int len1 = num1.length(); int len2 = num2.length(); int[] result = new int[len1 + len2]; for (int i = len1 - 1; i >= 0; i--) { for (int j = len2 - 1; j >= 0; j--) { multiply(num1.charAt(i), num2.charAt(j), result, i + j + 1); } } StringBuilder sb = new StringBuilder(); for (int i : result) { if (!(sb.length() == 0 && i == 0)) sb.append(i); } return sb.length() == 0 ? "0" : sb.toString(); } private void multiply(char c1, char c2, int[] result, int index) { int sum = (c1 - '0') * (c2 - '0') + result[index]; result[index] = sum % 10; result[index - 1] += sum / 10; }