Leetcode 43. Multiply Strings （python+cpp）

    class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0':
            return '0'
        # initialize the product as a list, the length of the product of these two num won't exceed the sum of length of num1 and num2
        product = [0] * (len(num1) + len(num2))
        # initialize the operation position, starting from the end of the product list
        pos = len(product) - 1
        for n1 in reversed(num1):
            # store the position for multiplying a single char in num1 with the entire num2
            curr_pos = pos
            for n2 in reversed(num2):
                # add the results at corresponding position
                product[curr_pos] += (ord(n1) - ord('0')) * (ord(n2) - ord('0'))
                # take care of the carry
                product[curr_pos - 1] += product[curr_pos] // 10
                product[curr_pos] %= 10
                curr_pos -= 1
            pos -= 1
        ans = ''
        # removed the starting 0s
        i = 0
        while i < len(product):
            if product[i] != 0:
                break
            i += 1
        while i < len(product):
            ans = ans + str(product[i])
            i += 1
        return ans

    class Solution:
    def multiply(self, num1: str, num2: str) -> str:    
        if num1 == '0' or num2 == '0':
            return '0'
        product = [0] * (len(num1) + len(num2))
        for i in range(len(num1)-1,-1,-1):
            for j in range(len(num2)-1,-1,-1):
                # compute multiplication of current two position
                res = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                # use i,j to find the correct position and take care of the carry
                product[i + j + 1] += res
                product[i + j] += product[i + j + 1] // 10
                product[i + j + 1] %= 10
                  
        ans = ''
        while i < len(product):
            if product[i] != 0:
                break
            i += 1
            
        while i < len(product):
            ans = ans + str(product[i])
            i += 1
        
        return ans

    class Solution {
    public:
    string singleMul(string num1,char d){
        string ans = "";
        int carry = 0;
        for(int i=num1.size()-1;i>=0;i--){
            auto c = num1[i];
            int res = (c-'0') * (d-'0') + carry;
            // cout << res << endl;
            carry = res / 10;
            ans = char((res%10) + '0') + ans;
        }
        if(carry) ans = char((carry+'0')) + ans;
        return ans;
    }
    string add(string num1,string num2){
        string ans = "";
        int carry = 0;
        int p1 = num1.size()-1;
        int p2 = num2.size()-1;
        
        while(p1 >= 0 || p2 >= 0){
            // cout << p1 << p2 << endl;
            int v1 = p1 >= 0 ? num1[p1] - '0' : 0;
            int v2 = p2 >= 0 ? num2[p2] - '0' : 0;
            
            ans = char((v1 + v2 + carry) % 10 + '0') + ans;
            // cout << ans << endl;
            carry = (v1 + v2 + carry) / 10;
            p1--;
            p2--;
        }
        if(carry) ans = char((carry+'0')) + ans;
        return ans;
    }
    string multiply(string num1, string num2) {
        // cout << singleMul("123",'5') << endl;
        if(num1 == "0" || num2 == "0") return "0";
        if(num2.size() == 1) return singleMul(num1,num2[0]);
        string ans = "0";
        for(int i = num2.size()-1;i>=0;i--){
            string tmp = singleMul(num1,num2[i]);
            for(int j=1;j<num2.size()-i;j++){
                tmp += "0";
            }
            // cout << tmp << endl;
            ans = add(ans,tmp);
            // cout << ans << endl;
        }
        return ans;
        // return "";
    }
    };