[leetcode]43. Multiply Strings

43. Multiply Strings

 

Given two non-negative integers num1 and num2represented as strings, return the product of num1and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3" Output: "6"

Example 2:

Input: num1 = "123", num2 = "456" Output: "56088"

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integerdirectly.

 

class Solution(object):
    def multiply(self, num1, num2):
        if num1 =="0" or num2 =="0":
            return "0"
        partialMult = []
        for i in range(len(num2)-1,-1,-1):
            cur_mult = [0 for _ in range(len(num2)-1-i)]
            n2 = int(num2[i])
            carry = 0
            
            for j in range(len(num1)-1,-1,-1):
                mult = n2 * int(num1[j]) + carry 
               
                carry = mult/10
                r = mult%10
                cur_mult.append(r)
            if carry >0:
                cur_mult.append(carry)
            partialMult.append(cur_mult)
        
       
        multSum = partialMult[0]
        for part in partialMult[1:]:
            carry = 0
            i = 0
            while i<len(multSum) or i<len(part) or carry>0:
                curSum = carry
                if i<len(multSum):
                    curSum +=multSum[i]
                if i<len(part):
                    curSum +=part[i]
                carry = curSum/10
                r = curSum%10
                if i < len(multSum):
                    multSum[i] = r
                else :
                    multSum.append(r)
                i+=1
        multSum.reverse()
        return ''.join(map(str,multSum))

차근차근 풀면 풀리는 문제지만

덜렁대면 절대 못푸는 문제이다.

우선 가장 오른쪽끝부터 계산해야한다는 점을 기억해야한다. 그래서 뒤에서부터 계산하는 연산과정을 넣어야하고

0을 체워넣을때에도 인덱스로 바로 하면안되고 뒤집어 있기때문에 len(num2)-1-i로 해서 체워넣어야한다.

그리고나서 partialMult를 처리할때에도 while문 을 or로 처리했기 때문에 i가 범위를 초과하는지를 꼭 체크해야하고

join은 문자열만 하기때문에 multSum이 integer로 이루어져있는것을 str로 변경후 concat해야한다.