Python 0415.py
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
l1 = len(num1)
l2 = len(num2)
if l1 < l2:
num1 = ("0" * (l2 - l1)) + num1
l1 = l2
if l2 < l1:
num2 = ("0" * (l1 - l2)) + num2
carry = 0
result = ""
for i in range(l1 - 1, -1, -1):
a = ord(num1[i]) - ord('0')
b = ord(num2[i]) - ord('0')
c = a + b + carry
if c >= 10:
carry = 1
c -= 10
else:
carry = 0
result += str(c)
if carry == 1:
result += "1"
# building in reverse is faster than prepending single digits a thousand times
return result[::-1]
Difficulty
and has an acceptance rate of about 52% (1+ million submissions).
Typical patterns to solve this problem:
- Math
- Simulation
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The implementation provides a method to add two non-negative integer values that are supplied as decimal strings. It works without converting the whole strings to integer types, thereby avoiding overflow for very large numbers. The algorithm proceeds by first equalizing the lengths of the two input strings, then iterating from the least significant digit toward the most significant digit while maintaining a carry flag, and finally producing the summed string in the correct order.
Normalizing Input Lengths
To simplify the digit-wise addition loop, the code ensures that both strings have the same length. If num1 is shorter, it is left-padded with the appropriate number of '0' characters; the same is done for num2 when it is shorter. The length variables l1 and l2 are updated accordingly.
l1 = len(num1)
l2 = len(num2)
if l1 < l2:
num1 = ("0" * (l2 - l1)) + num1
l1 = l2
if l2 < l1:
num2 = ("0" * (l1 - l2)) + num2
This step guarantees that the subsequent loop can index both strings at the same position without additional bounds checks.
Digitwise Addition Loop
The core of the algorithm iterates from the rightmost index (l1 - 1) down to 0. For each position, the characters are converted to their numeric values by subtracting the ASCII code of '0'. The sum of the two digits and any existing carry is computed, the new digit to store is derived, and the carry for the next iteration is updated.
carry = 0
result = ""
for i in range(l1 - 1, -1, -1):
a = ord(num1[i]) - ord('0')
b = ord(num2[i]) - ord('0')
c = a + b + carry
if c >= 10:
carry = 1
c -= 10
else:
carry = 0
result += str(c)
The use of ord avoids the overhead of converting each character through higher-level functions, and the conditional adjustment of c keeps the digit within the range 0-9.
Final Carry Handling
After processing all digit positions, a remaining carry of 1 indicates that the sum has an extra most-significant digit. The code appends this digit to the result string.
if carry == 1:
result += "1"
This branch correctly handles cases such as adding "999" and "1" where the result length exceeds the original operand lengths.
Result Construction
During the loop, digits are appended to result in reverse order (least significant first). Rather than inserting at the front of the string for each iteration-a costly operation-the algorithm builds the string backwards and performs a single reversal at the end. This approach reduces the number of memory reallocations and copies.
# building in reverse is faster than prepending single digits a thousand times
return result[::-1]
The slice notation [::-1] creates a reversed copy of the accumulated string, delivering the final sum in the correct most-significant-to-least-significant order.
Edge Cases Addressed
The code gracefully handles inputs of differing lengths by padding the shorter string with leading zeros, ensuring that the addition loop never encounters an index out of range. It also correctly processes the scenario where the final addition generates an extra carry, guaranteeing that the resulting string reflects the true magnitude of the sum. Leading zeros in the original inputs are preserved through the padding step, and the final reversal eliminates any artificial zeros that might have been introduced at the front of the intermediate result.
ELI5 - Simplified Explanation
Imagine you have two towers made of number blocks, but they are different heights. The first thing that happens is adding some invisible zero blocks to the shorter tower so that both towers are the exact same height. This makes it much easier to stack them up properly.
Now, picture starting at the very bottom blocks of both towers. You add those two blocks together, plus any extra bit that might have carried over from the step before. If that total is ten or more, you keep a little note called a carry to add to the next pair of blocks above. You write down the last digit of your sum and move up to the next pair. You keep doing this all the way to the top of the towers.
If there is still a carry note left over after the very top block, you place one final block on top of everything. Because all the work was done from the bottom to the top, the result is currently sitting upside down. Flipping it over shows the final total for these two big numbers.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||||
| www | AlgoMonster | C++ | Java | Python | TS | |||||||
| WalkCCC | C++ | Java | Python | |||||||||
| leetcode.ca | C++ | Java | JS | Rust | Python | Go | TS | |||||
| LeetcodeHelp | C++ | Java | Python | |||||||||
| Progiez | C++ | Java | Python | |||||||||
| github | BigEggStudy | C# | ||||||||||
| black-shadows | C++ | |||||||||||
| charles-wangkai | Java | |||||||||||
| everthis | JS | |||||||||||
| fartem | Ruby | |||||||||||
| fpdjsns | C++ | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JS | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| qiyuangong | Java | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| suxrobGM | C# | |||||||||||
| varunu28 | Java | |||||||||||
| vli02 | C | |||||||||||
| yuanliu666 | Kotlin | |||||||||||
| zfang399 | C++ | |||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||
| WalkCCC | C++, Python, Java | |||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, Rust, TypeScript | |||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||
| Progiez | C++, Java, Python | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++, C++ | |||||||||||
| charles-wangkai | Java | |||||||||||
| everthis | JavaScript | |||||||||||
| fartem | Ruby | |||||||||||
| fpdjsns | C++ | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JavaScript | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| qiyuangong | Java | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| suxrobGM | C# | |||||||||||
| varunu28 | Java | |||||||||||
| vli02 | C | |||||||||||
| yuanliu666 | Kotlin | |||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 2: Add Two Numbers
- problem 43: Multiply Strings
- problem 989: Add to Array-Form of Integer
Solved On The Same Day
- problem 463: Island Perimeter
- problem 541: Reverse String II
- problem 1211: Queries Quality and Percentage
- problem 1251: Average Selling Price
- problem 1280: Students and Examinations
- problem 1327: List the Products Ordered in a Period
- problem 1378: Replace Employee ID With The Unique Identifier
- problem 1407: Top Travellers
- problem 1484: Group Sold Products By The Date
- problem 1517: Find Users With Valid E-Mails
- problem 1527: Patients With a Condition
- problem 1581: Customer Who Visited but Did Not Make Any Transactions
- problem 1587: Bank Account Summary II
- problem 1633: Percentage of Users Attended a Contest
- problem 1661: Average Time of Process per Machine
- problem 1667: Fix Names in a Table
- problem 1683: Invalid Tweets
- problem 1693: Daily Leads and Partners
- problem 1729: Find Followers Count
- problem 1731: The Number of Employees Which Report to Each Employee
- problem 1741: Find Total Time Spent by Each Employee
- problem 1757: Recyclable and Low Fat Products
- problem 1789: Primary Department for Each Employee
- problem 1795: Rearrange Products Table
- problem 1873: Calculate Special Bonus
- problem 1890: The Latest Login in 2020
- problem 1965: Employees With Missing Information
- problem 1978: Employees Whose Manager Left the Company
- problem 2356: Number of Unique Subjects Taught by Each Teacher
- problem 166: Fraction to Recurring Decimal
- problem 223: Rectangle Area
- problem 240: Search a 2D Matrix II
- problem 318: Maximum Product of Word Lengths
- problem 357: Count Numbers with Unique Digits
- problem 394: Decode String
- problem 1158: Market Analysis I
- problem 1341: Movie Rating
- problem 1492: The kth Factor of n
- problem 1498: Number of Subsequences That Satisfy the Given Sum Condition
- problem 1907: Count Salary Categories
- problem 1934: Confirmation Rate
- problem 2405: Optimal Partition of String
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality