Leetcode 43. String multiplication

Topic link

Note the “instructions” section of the requirements:

• Num1 and num2 contain only the numbers 0-9.
• Num1 and num2 do not begin with zero, except in the case of the number 0 itself.

The basic idea of solving the problem is straightforward, and it simulates the multiplication process.

Assuming the two strings are “12345” and “678”, compute “12345” times “600”, “12345” times “70”, plus the intermediate result of the previous step, then “12345” times “8”, plus the intermediate result of the previous step. Get the final result.

The code has been submitted for approval.

func multiply(num1 string, num2 string) string {
        // Empty string is meaningless
	if num1 == "" {
		panic("num1 is empty")}if num2 == "" {
		panic("num2 is empty")}if num1 == "0" || num2 == "0" { // If one of the numbers is 0, the result is 0
		return "0"
	}
        If one number is 1, the result is another number
        if num1 == "1" {
                return num2
        }
        if num2 == "1" {
                return num1
        }
        // Select a shorter length for subsequent optimization
	if len(num1) <= len(num2) {
		return multiplyImpl(num1, num2)
	}
	return multiplyImpl(num2, num1)
}

func multiplyImpl(sn, ln string) string {
	var(
		sl = len(sn)
		ll = len(ln)
                // res and TMP can be reused in the following loop
		res = make([]byte.1, ll)
		tmp = make([]byte.0, ll)
	)
	res[0] = '0'
	for i := 0; i < sl; i++ {
		tmp = mul(ln, sn[i], sl-i- 1, tmp[:0])
		res = add(res, tmp)
	}
        // Invert the elements in res so that left is high and right is low.
	for i, j := 0.len(res)- 1; i < j; i, j = i+1, j- 1 {
		res[i], res[j] = res[j], res[i]
	}
	return string(res)
}

// Note that the settlement results are placed in the order of []byte, with the lower left and the higher right.
// If an intermediate result is 123450,
// Place ['0','5','4','3','2','1'] in []byte.
func mul(m string, s byte, suffixZeroCount int, tmp []byte) []byte {
	if s == '0' {
		return append(tmp, '0')}for i := 0; i < suffixZeroCount; i++ {
		tmp = append(tmp, '0')}if s == '1' { // Can simplify processing
                for i := len(m)- 1; i >= 0; i-- {
                        tmp = append(tmp, m[i])
                }
                return tmp
        }
	var(
		r int
		sn = getN(s)
	)
	for i := len(m)- 1; i >= 0; i-- {
		x := sn*getN(m[i]) + r
		tmp = append(tmp, getB(x%10))
		r = x/10
	}
	if r > 0 {
		tmp = append(tmp, getB(r))
	}
	return tmp
}

// Two [] bytes are placed in the order of the left byte and the right byte.
func add(res, b []byte) []byte {
	bl := len(b)
	if bl == 1 && b[0] = ='0' {
		return res
	}
	var (
		i int
		j int
		r int
		al = len(res)
	)
	for i < al && j < bl {
		x := getN(res[i])+getN(b[j]) + r
		d := getB(x%10)
		if i < len(res) {
			res[i] = d
		} else {
			res = append(res, d)
		}
		r = x/10
		i++
		j++
	}
        var iEnd bool
	for i < al { // Handle the rest
		x := getN(res[i]) + r
		d := getB(x%10)
		if i < len(res) {
			res[i] = d
		} else {
			res = append(res, d)
		}
		r = x/10
		i++
                iEnd = true
	}
	for j < bl { // Handle the rest
		x := getN(b[j]) + r
		d := getB(x%10)
		if j < len(res) {
			res[j] = d
		} else {
			res = append(res, d)
		}
		r = x/10
		j++
	}
	if r > 0 { // If there is a carry
		d := getB(r)
                if iEnd {
                       if i < len(res) {
                               res[j] = d    
                       } else {
                               res = append(res, d)
                       }
                } else {
                       if j < len(res) {
                               res[j] = d
                       } else {
                               res = append(res, d)
                       }
	        }
	}
	return res
}

// Convert a character number to an integer
func getN(b byte) int {
	return int(b-'0')}// Convert integer numbers to characters
func getB(n int) byte {
	return byte(n)+'0'
}
Copy the code