Multiply Strings -- LeetCode

 
這道題屬於數值操作的題目，其實更多地是考察乘法運算的本質。基本思路是和加法運算還是近似的，只是進位和結果長度復雜一些。我們仍然是從低位到高位對每一位進行計算，假設第一個數長度是n，第二個數長度是m，我們知道結果長度為m+n或者m+n-1（沒有進位的情況）。對於某一位i，要計算這個位上的數字，我們需要對所有能組合出這一位結果的位進行乘法，即第1位和第i-1位，第2位和第i-2位，... ，然後累加起來，最後我們取個位上的數值，然後剩下的作為進位放到下一輪循環中。這個算法兩層循環，每層循環次數是O(m+n)，所以時間復雜度是O((m+n)^2)。算法中不需要額外空間，只需要維護一個進位變量即可，所以空間復雜度是O(1)。代碼如下：

public String multiply(String num1, String num2) {
    if(num1 == null || num2 == null || num1.length()==0 || num2.length()==0)
        return ;
    if(num1.charAt(0)=='0')
        return 0;
    if(num2.charAt(0)=='0')
        return 0;
    StringBuilder res = new StringBuilder();
    int num = 0;
    for(int i=num1.length()+num2.length();i>0;i--)
    {
        for(int j=Math.min(i-1,num1.length());j>0;j--)
        {
            if(i-j<=num2.length())
            {
                num += (int)(num1.charAt(j-1)-'0')*(int)(num2.charAt(i-1-j)-'0');
            }
        }
        if(i!=1 || num>0)
            res.append(num%10);
        num = num/10;
    }
    return res.reverse().toString();
}

實現中有兩個小細節，一個是循環中最後有一個if判斷，其實就是看最高一位是不是0（最高第二位不可能是0，除非兩個源字符串最高位帶有0），如果是就不需要加入字符串中了。另一個小問題是我們是由低位到高位放入結果串的，所以最後要進行一次reverse，因為是一個O(m+n)的操作，不會影響算法復雜度。