43. Multiply Strings

题目：

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

链接： http://leetcode.com/problems/multiply-strings/

4/15/2017

自己的想法太麻烦，抄别人的想法。直接用一个数组表示就清楚很多了

27ms, 91%

注意的问题：

1. 可以试试类似的题是否用长数组更好

2. 第12行k的起始位置

3. 第17-19行还需要加上result[k]之前的值

4. 第29行如何从int转为char

 1 public class Solution {
 2     public String multiply(String num1, String num2) {
 3         if (num1.equals("0") || num2.equals("0")) return "0";
 4         else if (num1.equals("1")) return num2;
 5         else if (num2.equals("1")) return num1;
 6         
 7         int length = num1.length() + num2.length();
 8         int[] result = new int[length];
 9         int k;
10 
11         for (int i = num1.length() - 1; i >= 0; i--) {
12             k = length - num1.length() + i;
13             int carry = 0;
14             int a = num1.charAt(i) - '0';
15             for (int j = num2.length() - 1; j >= 0; j--) {
16                 int b = num2.charAt(j) - '0';
17                 int current = result[k];
18                 result[k] = (a * b + carry + current) % 10;
19                 carry = (a * b + carry + current) / 10;
20                 k--;
21             }
22             int current = result[k];
23             result[k] = (carry + current) % 10;
24         }
25         char[] ret;
26         if (result[0] == 0) ret = new char[length - 1];
27         else ret = new char[length];
28         for (int i = 0; i < ret.length; i++) {
29             ret[i] = result[0] == 0? (char)(result[i + 1] + '0'): (char)(result[i] + '0');
30         }
31         String r = new String(ret);
32         return r;
33     }
34 }

别人的算法：

注意在i和j为下标计算时，结果数组的index为i + j和i + j + 1。而且这里都不需要carry也不需要最后的判断了，因为在内层循环体里面已经算出来了

https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation

 1 public String multiply(String num1, String num2) {
 2     int m = num1.length(), n = num2.length();
 3     int[] pos = new int[m + n];
 4    
 5     for(int i = m - 1; i >= 0; i--) {
 6         for(int j = n - 1; j >= 0; j--) {
 7             int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
 8             int p1 = i + j, p2 = i + j + 1;
 9             int sum = mul + pos[p2];
10 
11             pos[p1] += sum / 10;
12             pos[p2] = (sum) % 10;
13         }
14     }  
15     
16     StringBuilder sb = new StringBuilder();
17     for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
18     return sb.length() == 0 ? "0" : sb.toString();
19 }