Leetcode discuss: 415. Add Strings

Here is the post. 

C# Warmup practice on June 17, 2020

June 17, 2020
Introduction
I am working on one month preparation for Facebook phone screen on July 2020. I like to take some time to review all easy level algorithms in one of my blogs called "Do my easy level algorithm mistake have a name?". My blog is here. I like to review my practice with a recursive function, and stack overflow issues.

Problem statement
Given two nonnegative integer numbers as string, calculate sum of two numbers. Maximum length of string is less than 5100.

Case study
Given two numbers, "123", "4567", the sum of two number can be calculated by rightmost digit first, so digit 3 and digit 7 will be added first, carry is true. Since 3 + 7 = 10, the rightmost digit is 0. So subproblem is to add two string "12" and "456", add previous sum string to "1" which is carry digit, last is to concatenate the rightmost digit string.

Time complexity (added on June 17, 2020)
If string's length is large than 256, then it is possible to have stack overflow.

So by retrorespect, I should learn to ask myself a question, what is the maximum length of string, how to write a short solution to solve it without stack overflow.

My first practice in 2018
My first practice is here on Sept. 15, 2018 with stack overflow problem.

I will practice again using iterative solution. I will write the solution based on my last iterative solution, here is the link.

Here are highlights of my practice:

1. Design a for loop with backward iteration, two array's index position variable, one carry variable;
2. Take advice from comment, choose to write using String API Insert instead of Append;
3. Variable sumString initilized value should be "" instead of "0".
4. How to design a for statement with initializer, condition and intrator in much efficient way?
5. More on step 4, backward iteration, initializer should be i = length1 - 1 , j = length2 - 1;
6. More on step 4, condition has three checking: i >= 0 || j >=0 || carry = 1;
7. More on step 4, iterator: i--, j--;
8. I spent over 10 to 15 minutes to make it work, failed two test cases, "1" and "9" should be "10" but my code return is "0", so sumString = sumString.Insert(...), need to assign the string with inserted back to sumString
9. I need to write more code, and also review all C# string APIs.

Challenges
To be a competitive programmer, it is important to learn how to write a for loop or while loop in most efficient way, and also avoid lengthy code or redundant code.

Pracitce more C# string APIs. It is better to memorize all APIs first, so I can expedite my coding process.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _415_add_strings
{
    class Program
    {
        static void Main(string[] args)
        {
            var sum = AddStrings("1","9"); 
        }

        /// <summary>
        /// code review June 17, 2020
        /// My last practice is here:
        /// https://leetcode.com/problems/add-strings/discuss/170839/C-iterative-solution-using-a-for-loop
        /// The idea to add two string as integer is to add from rightmost digit first, backward 
        /// until no digit left in two numbers or no carry to handle
        /// </summary>
        /// <param name="number1"></param>
        /// <param name="number2"></param>
        /// <returns></returns>
        public static String AddStrings(String number1, String number2)
        {
            if (number1 == null || number1.Length == 0)
            {
                return number2;
            }

            if (number2 == null || number2.Length == 0)
            {
                return number1; 
            }

            var length1 = number1.Length;
            var length2 = number2.Length;
            int carry = 0;

            var sumString = "";

            // good style is to write decrement one loop, backward, from last one first
            for (int i = length1 - 1, j = length2 - 1; i >= 0 || j >= 0 || carry == 1; i--, j--)
            {
                var digit1 = i < 0 ? 0 : (number1[i] - '0');
                var digit2 = j < 0 ? 0 : (number2[j] - '0');

                var sum = digit1 + digit2 + carry;
                var digit = sum % 10;
                carry = sum >= 10 ? 1 : 0;

                if (sumString.Length == 0)
                {
                    sumString = digit.ToString();
                }
                else
                {
                    sumString = sumString.Insert(0, digit.ToString());  // Insert API instead of Append, assign to subString
                }
            }

            return sumString;
        }
    }
}