力ボタンブラシ問題43.文字列乗算(Java)


タイトル
文字列形式で表される非負の整数num 1とnum 2の2つを与え、num 1とnum 2の積を返し、それらの積も文字列形式で表される.
例1:
入力:num 1="2"、num 2="3"出力:"6"例2:
入力:num 1="123"、num 2="456"出力:"56088"説明:
num 1およびnum 2の長さは110未満である.num 1とnum 2には0-9の数字しか含まれていません.num 1およびnum 2は、数値0自体でない限り、ゼロで始まることはありません.BigIntegerなどの標準ライブラリの大数タイプや、入力を直接整数に変換して処理することはできません.
構想
アナログディジタル乗算の演算過程は,時間複雑度O(M*N)MNがそれぞれ2文字列の長さであり,空間複雑度はO(M+N)である.各人は乗算して比較する必要があります.
に答える
class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return "0";
        int len = num1.length()+num2.length(),flag = 0;
        int[] data = new int[len];
        StringBuilder res = new StringBuilder();
        for (int i = num1.length()-1; i >=0 ; i--) {
            for (int j = num2.length()-1; j >=0 ; j--) {
                data[i+j+1] += (num1.charAt(i) -'0')*(num2.charAt(j)-'0');
                if(data[i+j+1]>=10){
                    int tmp = data[i+j+1];
                    data[i+j+1] = tmp%10; //          
                    data[i+j] += tmp/10; //  
                }
            }

        }
        //       0 
        int k = 0;
        for (; k < len; k++) {
            if (data[k] != 0) break;
        }
        //  
        while(k<len) res.append(data[k++]);
        return res.toString();
    }

}