Add Strings
File Name: add_strings.py ```python from utilities.testUtils import solution_title, print_and_assert_new, getTestResult from utilities.commonUtils import timeComplexity, spaceComplexity
print('\n >>> 415. Add Two Strings') print(''' Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly. ''')
class addTwoStrings(object): def quick(self, num1, num2): result = str(int(num1) + int(num2)) return result def brute_force(self, num1, num2): result, carry = '', 0 num1_index, num2_index = len(num1) - 1, len(num2) - 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
solution = addTwoStrings() solution_title('Add Two Strings - Quick One') print_and_assert_new(solution.quick, '11', '123', expected='134') print_and_assert_new(solution.quick, '456', '77', expected='533') print_and_assert_new(solution.quick, '0', '0', expected='0') getTestResult('Add Two Strings - Quick One')
timeComplexity('O(n)', 'Near Linear but + Operators can be expensive for larger numbers') spaceComplexity('O(n)', 'Linear for storing the result string.')
solution_title('Add Two Strings - Brute Force') print_and_assert_new(solution.brute_force, '11', '123', expected='134') print_and_assert_new(solution.brute_force, '456', '77', expected='533') print_and_assert_new(solution.brute_force, '0', '0', expected='0') getTestResult('Add Two Strings - Brute Force')
solution_title('Add Two Strings - Time Optimized') print_and_assert_new(solution.timeOptimized, '11', '123', expected='134') print_and_assert_new(solution.timeOptimized, '456', '77', expected='533') print_and_assert_new(solution.timeOptimized, '0', '0', expected='0') getTestResult('Add Two Strings - Time Optimized')
timeComplexity('O(n + m)', 'Linear by doing key changes like Using a List (result_list), reversed and joined into a single string.\n Reversing a list is O(n), and joining is also O(n), resulting in an overall O(n)') spaceComplexity('O(n + m)', 'Linear due to primary space consumption is from result_list, which grows to size O(n + m). ')```