# 43. Multiply Strings

## 1.問題

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  將輸入的兩個字串轉為數字相乘並返回對應的字串
* function header, parameter
* test input
* 說明想法
  * 由於輸入的字串長度最常可能會到110, 即使用long也會overflow
  * 因此解題的思路是將輸入的兩個字串每個位數放到array中
    * 個位數是array的max length - 1,  因此0的地方可能是沒有值的 (填0)
    * 用一個grid儲存長除法的數字
      * 長度為2倍max length, 並用一個指標移動左右, 此指標在每次計算時reset
      * 記得要計算餘數,計算下一位時要加回餘數
    * Create 一個char array儲存回傳的值, 記得要讓array\[length] = 0
      * 記得要計算餘數
    * Create一個string, 由指標的位置起算

```
string aResult = string(&aOutput[aWriteIndex]);
```

* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    string multiply(string num1, string num2) {
        int aLen1 = num1.length();
        int aLen2 = num2.length();
        int aMaxLen = max(aLen1, aLen2);
        int aNum1[aMaxLen + 1];
        int aNum2[aMaxLen + 1];
        for (int i = 0; i < aMaxLen; i++) {
            aNum1[i] = 0;
            aNum2[i] = 0;
        }
        
        for (int i = 0; i < aLen1; i++) {
            aNum1[aMaxLen - 1 - i] = int(num1[aLen1 - 1 - i] - '0');
        }
        
        for (int i = 0; i < aLen2; i++) {
            aNum2[aMaxLen - 1 - i] = int(num2[aLen2 - 1 - i] - '0');
        }
        
        //grid
        int aGridWidth = aMaxLen * 2;
        int aGridHeight = aMaxLen * 2;
        int aGrid[aGridWidth][aGridHeight];
        for (int i = 0; i < aGridWidth; i++) {
            for (int j = 0; j < aGridHeight; j++) {
                aGrid[i][j] = 0;
            }
        }
        
        //caculate grid
        int aCarry = 0, aWriteIndex = 0;
        for (int aDigit2 = aMaxLen - 1; aDigit2 >= 0; aDigit2--) {
            aCarry = 0;
            aWriteIndex = aGridWidth - aMaxLen + aDigit2;
            for (int aDigit1 = aMaxLen - 1; aDigit1 >= 0; aDigit1--) {
                int aProduct = aNum1[aDigit1] * aNum2[aDigit2] + aCarry;
                aGrid[aWriteIndex--][aDigit2] = (aProduct % 10);
                aCarry = aProduct / 10;
            }
            
            while (aCarry % 10 != 0) {
                aGrid[aWriteIndex--][aDigit2] = (aCarry % 10);
                aCarry /= 10; 
            }
        }
        
        
        
        //caculate output
        char aOutput[aGridWidth + 1];
        aOutput[aGridWidth] = 0;
        aWriteIndex = aGridWidth - 1;
        for (int i = aGridWidth - 1; i >=0; i--) {
            int aSum = aCarry;
            for (int j = 0; j < aGridHeight; j++) {
                aSum += aGrid[i][j];
            }
            aOutput[aWriteIndex--] = char((aSum % 10) + '0');
            aCarry = (aSum / 10);
        }
        
        while (aCarry != 0) {
            aOutput[aWriteIndex--] = char((aCarry % 10) + '0');
            aCarry /= 10; 
        }
        
        //Prevent underflow.
        if (aWriteIndex < 0) { 
            aWriteIndex = 0; 
        }
        
        //Chop off the leading zeroes...
        while (aWriteIndex < (aGridWidth - 1) && aOutput[aWriteIndex] == '0') {
            aWriteIndex += 1;
        }
        
        //Inset by our chopped zeroes...
        string aResult = string(&aOutput[aWriteIndex]);
        
        return aResult;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/43.-multiply-strings.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.