Multiply Strings

题目地址：
https://leetcode.com/problems/multiply-strings/#/description

题目：

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

Note:

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

解题思路：
这道题需要注意的是用dynamic programming。然后需要用两个指针分别从两个string的后面开始扫，然后需要用p1=i+j和p2=i+j+1两个指针来将值放进dp里面。需要注意的是进位问题。


代码：

public String multiply(String num1, String num2) {
    int m = num1.length();
    int n = num2.length();
    int[] dp = 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;
            int p2 = p1 + 1;
            int temp = dp[p2] + mul;
            int v1 = temp / 10;
            int v2 = temp % 10;
            dp[p1] += v1;
            dp[p2] = v2;
        }
    }
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i <= dp.length - 1; i++){
        if(!(sb.length() == 0 && dp[i] == 0)){
            sb.append(dp[i]);
        }
    }
    return sb.length() == 0 ? "0" :sb.toString();
}