Multiply Strings

• Time : $O(nm)$
• Space : $O(n + m)$

string Solution::multiply(string A, string B) {
    int n = A.length(), m = B.length();
    string res = string(n + m + 10, '0');
    reverse(begin(A), end(A));
    reverse(begin(B), end(B));
    for(int i = 0; i < n; i++) {
        int carry = 0;
        for(int j = 0; j < m; j++) {
            int now = carry + (A[i]-'0') * (B[j]-'0') + res[i+j] - '0';
            carry = now / 10;
            now %= 10;
            res[i+j] = now + '0';
        }
        int pos = i + m;
        while(carry) {
            int now = carry + res[pos] - '0';
            carry = now / 10;
            now %= 10;
            res[pos++] = now + '0';
        }
    }
    
    while(res.back() == '0') res.pop_back();
    reverse(begin(res),end(res));
    return res == "" ? "0" : res;
}