43. Multiply Strings Leetcode Java

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Solution:

First of all, a num with length of l1 multiply another num with length of l2, the product length will be l1+l2-1 or l1+l2, in order to avoid processing the leading zero, we will calculate the result only to l1+l2-1 and check if the last position is zero. 

The multiplication is straightforward, for ith digit, we have to calculate the product of 1st digit of num 1 and ith digit of num2 and 2en digit of num1 and i-2th digit of num2 ....and sum all this product, we use a variable carry to store the carry information to next digit.

Tip: The smallest digit is the last index of the string, so start from last char to first char for two numbers. Also, need to reverse the final result string.
Time complexity: O(m*n) 

 public String multiply(String num1, String num2) {  
     if(num1==null || num2==null || num1.length()==0||num2.length()==0) return null;  
     if(num1.charAt(0)=='0' || num2.charAt(0)=='0') return "0";  
     StringBuilder res=new StringBuilder();  
     int l1=num1.length();  
     int l2=num2.length();  
     int l=l1+l2-1;  
     int carry=0;  
     for(int i=0;i<l;i++){  
       int sum=carry;  
       for(int j=0;j<=i && j<l1;j++){  
         int a1=num1.charAt(l1-1-j)-'0';  
         int a2=(i-j>=l2)? 0: num2.charAt(l2-1-i+j)-'0';  
         sum+=a1*a2;  
       }  
       res.append(sum%10);  
       carry=sum/10;  
     }  
     if(carry!=0) res.append(carry);  
     return res.reverse().toString();  
   }