---
tags: LeetCode
---

# 415. Add Strings
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The **length of both num1 and num2** is < 5100.
2. Both num1 and num2 contains **only digits 0-9**.
3. Both num1 and num2 does **not contain any leading zero**.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

輸入範本如下

public class Solution {
    public string AddStrings(string num1, string num2) {
        
    }
}

### 直覺想法
- Note 1 代表最後回傳的答案會超過 int 能表示的範圍. 因此不可能使用 int 變數去暫存.
- Note 2 & 3 代表測資都會是合法的數字 , 只是以字串型式儲存.

依照我們平常加法的邏輯 , 將兩個數字擺在一起 , 若是有溢位 , 則代表下一次要多加一

- 使用字串儲存計算結果.
- 不論是使用 ( insert ) or ( + ) 複雜度都不好.
- 大量字串的處理 , 不適合使用 string .

104 ms	47.1 MB
You are here!
Your runtime beats 57.04 % of csharp submissions.
public string AddStrings(string num1, string num2)
    {
        string ans = string.Empty;
        for (int i = num1.Length - 1, j = num2.Length - 1, carry = 0; i >= 0 || j >= 0 || carry > 0; i--, j--)
        {
            int sum = 0;
            if (i >= 0) sum += num1[i] - '0';
            if (j >= 0) sum += num2[j] - '0';
            ans = ((sum + carry) % 10) + ans;
            carry = (sum + carry) / 10;
        }
        return ans.ToString();
    }

116 ms	47.5 MB
You are here!
Your runtime beats 23.59 % of csharp submissions.
public string AddStrings(string num1, string num2)
{
     string ans = string.Empty;
     for (int i = num1.Length - 1, j = num2.Length - 1, carry = 0; i >= 0 || j >= 0 || carry > 0; i--, j--)
     {
          int sum = 0;
          if (i >= 0) sum += num1[i] - '0';
          if (j >= 0) sum += num2[j] - '0';
          ans = ans.Insert(0, ((sum + carry) % 10).ToString());
          carry = (sum + carry) / 10;
     }
}

- 改使用 StringBuilder 儲存計算結果.
- 速度比使用 String 快很多.
- 與上面使用 String 比較 , 可以發現使用 Insert 的效率都不好.

96 ms	25.6 MB
You are here!
Your runtime beats 72.89 % of csharp submissions.
public string AddStrings(string num1, string num2)
{
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = num1.Length - 1, j = num2.Length - 1, carry = 0; i >= 0 || j >= 0 || carry > 0; i--, j--)
    {
        int sum = 0;
        if (i >= 0) sum += num1[i] - '0';
        if (j >= 0) sum += num2[j] - '0';
        stringBuilder.Append(((sum + carry) % 10));
        carry = (sum + carry) / 10;
    }
    return new string(stringBuilder.ToString().Reverse().ToArray());
}

100 ms	26 MB
You are here!
Your runtime beats 65.14 % of csharp submissions.
public string AddStrings(string num1, string num2)
{
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = num1.Length - 1, j = num2.Length - 1, carry = 0; i >= 0 || j >= 0 || carry > 0; i--, j--)
    {
        int sum = 0;
        if (i >= 0) sum += num1[i] - '0';
        if (j >= 0) sum += num2[j] - '0';
        stringBuilder.Insert(0, ((sum + carry) % 10));
        carry = (sum + carry) / 10;
    }
    return stringBuilder.ToString();
}

- 使用 char[] 儲存計算結果
- 每一輪運算皆少了 int 轉型的操作.

72 ms	24.7 MB
You are here!
Your runtime beats 100.00 % of csharp submissions.
public string AddStrings(string num1, string num2)
{
    int length = Math.Max(num1.Length, num2.Length) + 1;
    char[] result = new char[length];
    for (int i = num1.Length - 1, j = num2.Length - 1, ansIndex = length - 1, carry = 0; i >= 0 || j >= 0 || carry > 0;)
    {
        int sum = 0;
        if (i >= 0) sum += num1[i--] - '0';
        if (j >= 0) sum += num2[j--] - '0';
        result[ansIndex--] = (char)((sum + carry) % 10 + '0');
        carry = (sum + carry) / 10;
    }
    // char 型態的初始值是 '\0' 
    return result.First() == '\0' ? new string(result, 1, result.Length - 1) : new string(result);
}

### 參考
[NULL，0，'\0'，"\0"，"0"你分得清嗎](https://kknews.cc/tech/6avqgrp.html)

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: