康瑞部落

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.

解题思路：

按照小学的做法，每位相加即可。这里我定义了两个函数：strMul和strAdd，分别表示字符串与字符相乘，两个字符串相加。需要注意的是其中一个乘数为0的情况，返回的并不是“000”，而是“0”

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0"){
            return "0";
        }
        int len=num2.length();
        
        string result = "";
        
        int i = len-1;
        int zero=0;    //中间结果需要增加的0的数目
        while(i>=0){
            string tempResult = strMul(num1, num2[i]);
            for(int j=0; j<zero; j++){
                tempResult += "0";
            }
            result = strAdd(result, tempResult);
            i--;
            zero++;
        }
        
        return result;
    }
    
    string strMul(const string& num, char c){
        int len = num.length();
        int iC = c - '0';
        int carry=0;
        
        string result="";
        
        int i=len - 1;
        while(i>=0){
            int total = (num[i] - '0') * iC + carry;
            result = (char)(total%10 + '0') + result;
            carry = total/10;
            i--;
        }
        if(carry>0){
            result = (char)(carry + '0') + result;
        }
        
        return result;
    }
    
    string strAdd(const string& num1, const string& num2){
        int len1=num1.length();
        int len2=num2.length();
        int carry=0;
        int i=len1-1, j=len2-1;
        
        string result="";
        while(i>=0&&j>=0){
            int total = (num1[i]-'0') + (num2[j]-'0') + carry;
            result =(char)(total%10 + '0') + result;
            carry = total/10;
            i--;
            j--;
        }
        while(i>=0){
            int total = (num1[i]-'0') + carry;
            result = (char)(total%10 + '0') + result;
            carry = total/10;
            i--;
        }
        while(j>=0){
            int total = (num2[j]-'0') + carry;
            result = (char)(total%10 + '0') + result;
            carry = total/10;
            j--;
        }
        
        if(carry>0){
            result =(char)(carry + '0') + result;
        }
        
        return result;
    }
};

这里在leetcode中的时间比较多，主要是字符串不断拼接开销比较大，花费87ms。可以改成下列代码，只需要10ms：

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1=num1.length();
        int len2=num2.length();
        
        string result(len1 + len2 + 1, '0');
        
        int i = len2-1;
        int offset = 0;
        while(i>=0){
            strMul(num1, num2[i], result, offset);
            i--;
            offset++;
        }
        
        int len = result.length();
        i = 0;
        while(i<len){
            if(result[i]=='0'){
                i++;
            }else{
                break;
            }
        }
        
        if(i==len){    //结果为0的情况
            return "0";
        }
        
        return i>0 ? result.substr(i) : result;
    }
    
    void strMul(const string& num, char sc, string& result, int offset){
        int c = sc - '0';
        int carry=0;
        
        int i=num.length() - 1;
        int j=result.length()-1 - offset;
        while(i>=0){
            int total = (num[i] - '0') * c + carry + (result[j] - '0');
            carry = total/10;
            result[j] = total%10 + '0';
            i--;
            j--;
        }
        while(carry>0){
            int total = carry + (result[j] - '0');
            carry = total/10;
            result[j] = total%10 + '0';
            j--;
        }
    }
};