C++ O(mn) 8ms solution


  • 0
    A
    class Solution {
    public:
        string multiply(string num1, string num2) {
            if (num1 == "0" || num2 == "0") return "0";
            int size1 = num1.size(), size2 = num2.size();
            string ans(size1 + size2, '0');
            reverse(num1); reverse(num2);
            for (int i = 0; i < size1; ++i){
                int carry = 0, digit1 = num1[i] - '0';
                for (int j = 0; j < size2; ++j){
                    int digit2 = num2[j] - '0', res = ans[i+j] - '0', product = digit1 * digit2;
                    int sum = res + carry + product;
                    res = sum % 10;
                    carry = sum / 10;
                    ans[i+j] = '0' + res;
                }
                int digit = ans[i + size2] - '0';
                if (digit + carry < 10) ans[i + size2] = '0' + digit + carry;
                else{
                    ans[i + size2] = '0' + (digit + carry) % 10;
                    ans[i + size2 + 1] = '1';
                }
            }
            reverse(ans);
            int i = 0;
            while (ans[i] == '0') ++i;
            return ans.substr(i, size1 + size2);
        }
        
        void reverse(string& s){
            int n = s.size();
            int step = 0, i = 0, j = n-1;
            while (step < n / 2){
                s[i] ^= s[j] ^= s[i] ^= s[j];
                ++i; --j;
                ++step;
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.