乗算文字列Leetcodeソリューション


難易度 ミディアム
よく聞かれる Amazon (アマゾン) Apple ByteDance エクスペディア Facebook Google Houzz Mathworks社 マイクロソフト オラクル 正方形である Twitter ユーバー Zillowは
数学 文字列

問題のMultiplyStrings Leetcodeソリューションでは、入力として与えられたXNUMXつの文字列を乗算するように求められます。 この乗算の結果を出力するか、呼び出し元の関数に返す必要があります。 したがって、XNUMXつの文字列をより正式に指定するには、指定された文字列の積を見つけます。 これら ストリング 多くの桁を持つことができます。 したがって、与えられた文字列を単純に整数に変換してから、単純な乗算を使用しようとしないでください。 理解を深めるために、いくつかの例を見てみましょう。

First String: "2"
Second String: "3"
Resultant String: "6"

説明:両方のストリングが6桁しかないためです。 出力がXNUMXである必要があることを確認できます。

First String: "123"
Second String: "456"
Resultant String: "56088"

説明:この例でも、56088つのストリングが提供されており、これらのストリングを乗算して「XNUMX」を算出します。

First String: "123"
Second String: "0"
Resultant String: "0"

説明:ここでは、「000」または「00」を印刷しませんでした。 結果が0の場合、単一の「0」を出力する必要があります。

First String: "123456789"
Second String: "987654321123456789987"
Resultant String: "121932631127876847872042371743"

説明:ここで、この例では、数値データ型で保存できなかった大きな文字列を出力として与えるために乗算されるXNUMXつの文字列が与えられています。 したがって、この例は、私たちのアルゴリズムが処理できるはずの数少ない例のXNUMXつです。

乗算文字列リートコードソリューションのためのブルートフォースアプローチ

文字列の乗算LeetcodeSolutionの問題は、XNUMXつの指定された文字列を乗算するように要求しただけです。 だから、なぜ私たちはそれだけをしないのですか? まあ、それをうまく実装するのは少し難しいです。 しかし、XNUMXつの数値を乗算するために使用した方法を思い出すと、ここでも同じ手法を簡単に使用できます。

したがって、このアプローチでは、指定された文字列の1つを右から左にトラバースします。 インデックスまたは文字にいるときは、他の文字列全体にこの現在の文字を掛けます。 乗算が完了したら、その最後にゼロを追加します。 追加されるゼロの数は、文字列内の現在の文字の末尾からの位置– XNUMXに等しくなります。ゼロの追加が完了したら、この文字列を結果に追加します。 したがって、最初の文字列の右から左にトラバースすると、結果の文字列に回答が格納されます。

ブルートフォースコード

乗算文字列LeetcodeソリューションのC ++コード

#include <bits/stdc++.h>
using namespace std;

inline string add_zero(int n){
    string res = "";
    while(n-- > 0)res += "0";
    return res;
}

string add_string(string& a, string& b){
    if(a.size()>b.size())swap(a,b);
    int a_len = a.size(), b_len = b.size();
    string res = "";
    int sum = 0, carry = 0;
    for(int i=0;i<b_len;i++){
        int a_idx = a_len-1-i, b_idx = b_len-1-i;
        sum = carry + (a_idx>=0 ? (a[a_idx]-'0') : 0) + (b[b_idx]-'0');
        carry = sum/10; sum %= 10;
        res += to_string(sum);
    }
    if(carry>0)
        res += to_string(carry);
    reverse(res.begin(), res.end());
    return res;
}

string multiply(string num1, string num2) {
    if(num1 == "0" || num2 == "0")
        return "0";
    string res = "";
    if(num1.size()>num2.size())swap(num1, num2);
    int num1_len = num1.size(), num2_len = num2.size();
    for(int i=num1_len-1;i>=0;i--){
        int multiplier = num1[i]-'0';
        int sum = 0, carry = 0;
        string cur_res = "";
        for(int j=num2_len-1;j>=0;j--){
            sum = carry + (num2[j]-'0')*multiplier;
            carry = sum/10; sum %= 10;
            cur_res += to_string(sum);
        }
        if(carry>0)
            cur_res += to_string(carry);
        reverse(cur_res.begin(), cur_res.end());
        cur_res += add_zero(num1_len-i-1);
        res = add_string(res, cur_res);
    }
    return res;
}

int main(){
    string num1 = "123";
    string num2 = "456";
    cout<<multiply(num1, num2);
}
56088

乗算文字列LeetcodeソリューションのJavaコード

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
     private static String add_zero(int n){
        String res = "";
        while(n-- > 0)res += "0";
        return res;
    }
    
    private static String add_string(String a, String b){
        if(a.length()>b.length()){
            String tmp = a;
            a = b;
            b = tmp;
        }
        int a_len = a.length(), b_len = b.length();
        String res = "";
        int sum = 0, carry = 0;
        for(int i=0;i<b_len;i++){
            int a_idx = a_len-1-i, b_idx = b_len-1-i;
            sum = carry + (a_idx>=0 ? (a.charAt(a_idx)-'0') : 0) + (b.charAt(b_idx)-'0');
            carry = sum/10; sum %= 10;
            res += Integer.toString(sum);
        }
        if(carry>0)
            res += Integer.toString(carry);
        StringBuilder sb = new StringBuilder(res);
        sb.reverse();
        return sb.toString();
    }
    
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        String res = "";
        if(num1.length()>num2.length()){
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        int num1_len = num1.length(), num2_len = num2.length();
        for(int i=num1_len-1;i>=0;i--){
            int multiplier = num1.charAt(i)-'0';
            int sum = 0, carry = 0;
            String cur_res = "";
            for(int j=num2_len-1;j>=0;j--){
                sum = carry + (num2.charAt(j)-'0')*multiplier;
                carry = sum/10; sum %= 10;
                cur_res += Integer.toString(sum);
            }
            if(carry>0)
                cur_res += Integer.toString(carry);
            StringBuilder sb = new StringBuilder(cur_res);
            sb.reverse();
            sb.append(add_zero(num1_len-i-1));
            res = add_string(res, sb.toString());
        }
        return res;
    }
    
    public static void main(String[] args){
    	String num1 = "123";
    	String num2 = "456";
    	System.out.println(multiply(num1, num2));
    }
}
56088

複雑さの分析

時間の複雑さ

O(N * M)、 ここで、Nは最初の文字列のサイズ、MはXNUMX番目の文字列のサイズです。

スペースの複雑さ

O(N + M)、 結果をN + Mのサイズを持つことができる別の文字列に保存したためです。 したがって、空間の複雑さは線形です。

乗算文字列の最適化されたアプローチLeetcodeソリューション

最適化されたアプローチは、最初に観察するのが少し難しいです。 最適化されたアプローチも、上記のブルートフォースアプローチと同じ時間計算量を持ちますが、文字列を逆にし、結果の各中間文字列を回答に追加するオーバーヘッドコストを排除します。 最適化されたアプローチでは、両方の文字列の各桁を乗算します。 したがって、インデックスの各ペアを検討します。一方のインデックスは最初の文字列からのもので、もう一方は1番目の文字列からのものです。 インデックスがそれぞれXNUMX番目とXNUMX番目の文字列でi、jである場合、結果の文字列でi + j、i + j +XNUMXインデックスを取得するという考え方です。 したがって、この事実を使用して、中間文字列の追加、ゼロの追加、中間文字列の反転で失われていたオーバーヘッドを取り除くことができます。これにより、ソリューションが大幅に高速化されます。 下の画像を見るとわかりやすくなります。

乗算文字列Leetcodeソリューション

最適化されたコード

乗算文字列LeetcodeソリューションのC ++コード

#include <bits/stdc++.h>
using namespace std;

string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0")
            return "0";
        if(num1.size()>num2.size())swap(num1, num2);
        int num1_len = num1.size(), num2_len = num2.size();
        int res[num1_len+num2_len];memset(res, 0, sizeof res);
        for(int i=num1_len-1;i>=0;i--){
            for(int j=num2_len-1;j>=0;j--){
                int p1 = i+j, p2 = p1+1;
                int sum = (num1[i]-'0')*(num2[j]-'0') + res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        string output = ""; int idx = -1;
        for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
            idx = i;
        for(int i=idx+1;i<num1_len+num2_len;i++)
            output += to_string(res[i]);
        return output;
    }

int main(){
    string num1 = "123";
    string num2 = "456";
    cout<<multiply(num1, num2);
}
56088

乗算文字列のJavaコードLeetcodeソリューション

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        if(num1.length()>num2.length()){
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        int num1_len = num1.length(), num2_len = num2.length();
        int res[] = new int[num1_len+num2_len];
        Arrays.fill(res, 0);
        for(int i=num1_len-1;i>=0;i--){
            for(int j=num2_len-1;j>=0;j--){
                int p1 = i+j, p2 = p1+1;
                int sum = (num1.charAt(i)-'0')*(num2.charAt(j)-'0') + res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        String output = ""; int idx = -1;
        for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
            idx = i;
        for(int i=idx+1;i<num1_len+num2_len;i++)
            output += Integer.toString(res[i]);
        return output;
    }
    
    public static void main(String[] args){
    	String num1 = "123";
    	String num2 = "456";
    	System.out.println(multiply(num1, num2));
    }
}
56088

複雑さの分析

時間の複雑さ

O(N * M)、 複雑さはブルートフォース方式と同じですが、オーバーヘッドコストを取り除くと、パフォーマンスが大幅に向上します。

スペースの複雑さ

O(N + M)、 結果の文字列のサイズはN + Mであるためです。ここで、Nは最初の文字列のサイズであり、MはXNUMX番目の文字列のサイズです。