(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.

Thoughts:
This is not a hard question in the sense that there’s no “clever” algorithm to apply. We just do the intuitive way. Think about how we human being multiply two integers. We take each digit and multiply it with another digit, then the addition, taking care of the carry. So we just “mimic” that method in our code. The only catch is that we have to be busy travelling between integer and char. Another catch is how much space we should initialize our result string. Well, in my solution, I try to be conservative to find the upper bound – the number of digits of the products can be no more than the sum of the digits of the two multipliers. In the end, we might find we allocated more space than we need to, resulting some leading zeros. We can just clean it up.

Code (Java):

public class Solution {
    public String multiply(String num1, String num2) {
        char[] result = new char[num1.length() + num2.length()];
        for(int i = 0; i < result.length; ++i)
            result[i] = '0';
        for(int i = num1.length() - 1; i >= 0; --i) {
            int index = num1.length() + num2.length() - 1 - (num1.length() - 1 - i);
            int digit1 = Character.getNumericValue(num1.charAt(i));
            for(int j = num2.length() - 1; j >= 0; --j) {
                int digit2 = Character.getNumericValue(num2.charAt(j));
                int temp = digit1 * digit2;
                int previous = Character.getNumericValue(result[index]);
                result[index] = (char) ((previous + temp) % 10 + '0');
                int carry = (previous + temp) / 10;
                int m = index - 1;                
                while(carry != 0 && m >= 0) {
                    int rm = Character.getNumericValue(result[m]);
                    result[m] = (char)((rm + carry) % 10 + '0');
                    carry = (rm + carry) / 10;
                    m--;
                }
                
                index--;
            }
        }
        return new String(result).replaceFirst("^0+(?!$)", "");
    }
}

Code (C++):
class Solution {
public:
    string multiply(string num1, string num2) {
        char result[num1.size() + num2.size()];
        for(int i = 0; i < num1.size() + num2.size(); ++i)
            result[i] = '0';
        for(int i = num1.size() - 1; i >= 0; --i) {
            int index = num1.size() + num2.size() - 1 - (num1.size() - 1 - i);
            int digit1 = num1[i] - '0';
            for(int j = num2.size() - 1; j >= 0; --j) {
                int digit2 = num2[j] - '0';
                int temp = digit1 * digit2;
                int previous = result[index] - '0';
                result[index] = (char) ((previous + temp) % 10 + '0');
                int carry = (previous + temp) / 10;
                int m = index - 1;                
                while(carry != 0 && m >= 0) {
                    int rm = result[m] - '0';
                    result[m] = (char)((rm + carry) % 10 + '0');
                    carry = (rm + carry) / 10;
                    m--;
                }
                
                index--;
            }
        }
        string candidate = string(result, num1.size() + num2.size());
        size_t i = candidate.find_first_not_of('0');
        return i ==  string::npos ? "0" : candidate.substr(i);
    }
};