My ac solution with 11ms


  • 1
    S
    class Solution {
    public:
        string multiply(string num1, string num2) {
            int len1 = num1.length();
            int len2 = num2.length();
            if(len1 <= 0 || len2 <= 0){
                return "";
            }//if
            int sum = 0;
            int len3 = len1 + len2;
            char result[len3];
            memset(result,'0',sizeof(result[0])*(len3+1));
            for(int i = len1 - 1,m = 0;i >= 0;--i,++m){
                for(int j = len2 - 1,n = 0;j >= 0;--j,++n){
                    sum = (num1[i] - '0') * (num2[j] - '0') + result[m+n] - '0';
                    result[m+n] = sum % 10 + '0';
                    result[m+n+1] += sum / 10;
                }//for
            }//for
            // 0
            while(result[len3] == '0' && len3 > 0){
                --len3;
            }//while
            //the end of result:'\0'
            result[len3+1] = '\0';
            // reverse
            int temp;
            for(int i = 0,j = len3;i < j;++i,--j){
                temp = result[i];
                result[i] = result[j];
                result[j] = temp;
            }//for
            return string(result);
        }
    };

  • 1
    J

    Thanks. It is tricky to predict the length of the result string. len(999…×999…) <= len(1000…) + len(1000…) - 1

    The STL version:

    class Solution {
    public:
        string multiply(string a, string b) {
            if (a.empty() || b.empty()) return "";
            string result(a.length() + b.length(), '0');
            int i = 0;
            for (auto p = a.rbegin(); p != a.rend(); p++, i++) {
                int j = 0;
                for (auto q = b.rbegin(); q != b.rend(); q++, j++) {
                    int t = (*p - '0') * (*q - '0') + (result[i+j] - '0');
                    result[i+j] = (t % 10) + '0';  // digit
                    result[i+j+1] += t / 10;  // carry
                }
            }
            while (result.length() > 1 && result.back() == '0') {
                result.pop_back();
            }
            reverse(result.begin(), result.end());
            return result;
        }
    };

  • 0
    C

    This is very elegant solution !


Log in to reply
 

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