43. Multiply Strings

题目描述(中等难度)

就是两个数相乘，输出结果，只不过数字很大很大，都是用 String 存储的。也就是传说中的大数相乘。

直接看代码。

public class Multiply_Strings {
	
	public static String multiply(String num1, String num2) {
	    if (num1.equals("0") || num2.equals("0")) {
	        return "0";
	    }
	    int n1 = num1.length();
	    int n2 = num2.length();
	    int[] pos = new int[n1 + n2]; //保存最后的结果
	    for (int i = n1 - 1; i >= 0; i--) {
	        for (int j = n2 - 1; j >= 0; j--) {
	            //相乘的结果
	            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
	            //加上 pos[i+j+1] 之前已经累加的结果
	            int sum = mul + pos[i + j + 1];
	            //更新 pos[i + j]
	            pos[i + j] += sum / 10;
	            //更新 pos[i + j + 1]
	            pos[i + j + 1] = sum % 10;
	        }
	    }
	    StringBuilder sb = new StringBuilder();
	    for (int i = 0; i < pos.length; i++) {
	        //判断最高位是不是 0 
	        if (i == 0 && pos[i] == 0) {
	            continue;
	        }
	        sb.append(pos[i]);
	    }
	    return sb.toString();
	}
	
	public static void main(String args[]) {
		String nums1="1123";
		String nums2="245";
		String ans=multiply(nums1,nums2);
		System.out.println(ans);
		
	}
}

时间复杂度：O（m * n）。m，n 是两个字符串的长度。

空间复杂度：O（m + n）。m，n 是两个字符串的长度。