# 0043. Multiply Strings
###### tags: `Leetcode` `FaceBook` `Medium`
Link: https://leetcode.com/problems/multiply-strings/
## 思路 O(M* N) O(M+N)
参考了[这篇](https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation)
简单来说第i位和第j位乘法的结果一定是在答案的i+j和i+j+1位

这个思路用了很多小trick，非常值得学习~
- 一个M位的数和一个N位的数乘，长度最长就是M+N
- 因为是从后面往前算的，并且如果第i+j+1位之前有值，会把第i位和第j位乘法的结果加在上面一起算，所以避免了overflow
- 另外遇到例如9999 * 0的情况，ans里面会变成00000，这时候如果不经过处理，返回的string就会是00000，处理的方法是**如果sb现在是空的，那么就不能把0放进去**
## Code

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] ans = new int[m+n];
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                int n1 = num1.charAt(i)-'0';
                int n2 = num2.charAt(j)-'0';
                int mul = n1*n2;
                int p1 = i+j;
                int p2 = i+j+1;
                mul += ans[p2];
                ans[p1] += mul/10;
                ans[p2] = mul%10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < ans.length;i++){
            if(!(sb.length()==0 && ans[i]==0)){
                sb.append(ans[i]);
            }
        }
        return sb.length()==0?"0":sb.toString();
    }
}