043._multiply_strings.md

###43. Multiply Strings

题目: https://leetcode.com/problems/multiply-strings/

难度:

Medium

思路：

虽然写了一堆similar problems，拿到的时候也算有思路，但是还是觉得很难写

参考了别人的思路：

1. m位的数字乘以n位的数字的结果最大为m+n位： 99999 < 1000100 = 100000，最多为3+2 = 5位数。
2. 先将字符串逆序便于从最低位开始计算。

觉得这样写才是最容易理解的，看一个具体的🌰:

123 * 456

	123
  * 456
  

先把每一位拿来相乘：得到
			1   2   3
		    4   5   6
		    
			6	12	18
		5	10	15
	4	8	12

这样在全部加起来和做进位处理
	5	6	0	8	8

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if num1 == '0' or num2 == '0' : return '0'
        len1,len2 = len(num1),len(num2)
        
        num1 = num1[::-1]
        num2 = num2[::-1]
        # 99 * 99 < 10000, maxmize 4 digit
        arr = [0 for i in range(len1 + len2)]

        for i in xrange(len1):
            for j in xrange(len2):
                arr[i+j] += (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))


        res = [0 for i in range(len1 + len2)]

        for i in range(len(arr)):
            res[i] = arr[i] % 10
            if i < len(arr) - 1:
                arr[i+1] += arr[i]/10
        
        i = len(arr)-1
        if res[i] == 0:
            i -= 1
        return ''.join(str(j) for j in res[:i+1][::-1])