This is the 11th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Given two string integers, return string integers.”

Title link:

Source: LeetCode

Link: 43. String Multiplication – LeetCode (leetcode-cn.com)

2

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, whose product is also represented as strings.

Example 1: Input: num1 = "2", num2 = "3" Output: "6"Copy the code
Example 2: Input: num1 = "123", num2 = "456" Output: "56088"Copy the code

Second, the problem solving

1. Analysis of ideas

This problem is to find two character creation form of integer product, you can use vertical multiplication to solve the problem, read character creation in each character to multiply.

For example, 38*38 = 38* 30 + 38* 8 = 1444

The next step is to convert the numbers in the string to ASCII. Characters 0-9 have ASCII values of 48-57.

Such as:

**’9′ – ‘5’ = 57-53 = 4 **

(char)(8 + ‘4’) =8+52=60=12

2. Code implementation

Code reference:

public class Solution {
    public string Multiply(string num1, string num2) {
        StringBuilder sum = new StringBuilder(new string('0', num1.Length + num2.Length));
        for (int i = num1.Length - 1; i >= 0; i--)
        {
            for (int j = num2.Length - 1; j >= 0; j--)
            {
              int next = sum[i + j + 1] - '0' + (num1[i] - '0') * (num2[j] - '0');
              sum[i + j + 1] = (char)(next % 10 + '0');
              sum[i + j] += (char)(next / 10); }}string res = sum.ToString().TrimStart('0');
        return res.Length == 0 ? "0": res; }}Copy the code

3. Time complexity

Time complexity: O(M N)

M and N are the lengths of num1 and num2 respectively.

Space complexity: O(M+N)

Used to store calculation results.

Third, summary

See, this is a lot like the convolution formula…

Algorithms often need the support of algorithmic formulas…