ಸ್ಟ್ರಿಂಗ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಗುಣಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆಪಲ್ ಬೈಟ್ ಡೇನ್ಸ್ Expedia ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಹೌಝ್ ಮ್ಯಾಥ್ವರ್ಕ್ಸ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ಸ್ಕ್ವೇರ್ ಟ್ವಿಟರ್ ಉಬರ್ ಝಿಲೋ
ಮಠ ಸ್ಟ್ರಿಂಗ್

ಮಲ್ಟಿಪ್ಲೈ ಸ್ಟ್ರಿಂಗ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ಎರಡು ತಂತಿಗಳನ್ನು ಗುಣಿಸಲು ಕೇಳುತ್ತದೆ, ಅದು ನಮಗೆ ಇನ್ಪುಟ್ ಆಗಿ ನೀಡಲಾಗುತ್ತದೆ. ಕಾಲರ್ ಕಾರ್ಯಕ್ಕೆ ಗುಣಿಸಿದಾಗ ಈ ಫಲಿತಾಂಶವನ್ನು ನಾವು ಮುದ್ರಿಸಬೇಕು ಅಥವಾ ಹಿಂದಿರುಗಿಸಬೇಕು. ಆದ್ದರಿಂದ ಎರಡು ತಂತಿಗಳನ್ನು ಹೆಚ್ಚು ly ಪಚಾರಿಕವಾಗಿ ನೀಡಲು, ಕೊಟ್ಟಿರುವ ತಂತಿಗಳ ಉತ್ಪನ್ನವನ್ನು ಹುಡುಕಿ. ಇವು ತಂತಿಗಳು ಅನೇಕ ಅಂಕೆಗಳನ್ನು ಹೊಂದಬಹುದು. ಆದ್ದರಿಂದ ಕೊಟ್ಟಿರುವ ತಂತಿಗಳನ್ನು ಪೂರ್ಣಾಂಕಗಳಾಗಿ ಪರಿವರ್ತಿಸಲು ಪ್ರಯತ್ನಿಸಬಾರದು ಮತ್ತು ನಂತರ ಸರಳ ಗುಣಾಕಾರವನ್ನು ಬಳಸಬಾರದು. ಉತ್ತಮ ತಿಳುವಳಿಕೆಗಾಗಿ ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

ಉದಾಹರಣೆಗಳು

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

ವಿವರಣೆ: ಎರಡೂ ತಂತಿಗಳು ಒಂದೇ ಅಂಕೆಗಳನ್ನು ಹೊಂದಿರುವುದರಿಂದ. Output ಟ್ಪುಟ್ 6 ಆಗಿರಬೇಕು ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬಹುದು ಮತ್ತು ಅದು ನಿಜ.

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

ವಿವರಣೆ: ಈ ಉದಾಹರಣೆಯಲ್ಲಿ, ನಮಗೆ ಎರಡು ತಂತಿಗಳನ್ನು ನೀಡಲಾಗುತ್ತದೆ, ನಂತರ ಅವುಗಳನ್ನು “56088” ನೀಡಲು ಗುಣಿಸಲಾಗುತ್ತದೆ.

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

ವಿವರಣೆ: ಇಲ್ಲಿ ನಾವು “000” ಅಥವಾ “00” ಅನ್ನು ಮುದ್ರಿಸಲಿಲ್ಲ. ಒಂದು ವೇಳೆ, ಫಲಿತಾಂಶವು 0 ಆಗಿದ್ದಾಗ, ನಾವು ಒಂದೇ “0” ಅನ್ನು ಮುದ್ರಿಸಬೇಕಾಗುತ್ತದೆ.

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

ವಿವರಣೆ: ಈಗ, ಈ ಉದಾಹರಣೆಯಲ್ಲಿ, ದೊಡ್ಡ ದಾರವನ್ನು output ಟ್‌ಪುಟ್‌ನಂತೆ ನೀಡಲು ಎರಡು ತಂತಿಗಳನ್ನು ನಮಗೆ ನೀಡಲಾಗಿದೆ, ಅದನ್ನು ಸಂಖ್ಯಾ ಡೇಟಾ ಪ್ರಕಾರದಲ್ಲಿ ಉಳಿಸಲಾಗಲಿಲ್ಲ. ಆದ್ದರಿಂದ, ಈ ಉದಾಹರಣೆಯು ನಮ್ಮ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಎದುರಿಸಲು ಸಮರ್ಥವಾಗಿರುವ ಕೆಲವೇ ಒಂದು.

ಗುಣಾಕಾರ ತಂತಿಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ವಿವೇಚನಾರಹಿತ ವಿಧಾನ

ಮಲ್ಟಿಪ್ಲೈ ಸ್ಟ್ರಿಂಗ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ಕೊಟ್ಟಿರುವ ಎರಡು ತಂತಿಗಳನ್ನು ಗುಣಿಸಲು ಕೇಳಿದೆ. ಆದ್ದರಿಂದ, ನಾವು ಅದನ್ನು ಏಕೆ ಮಾಡಬಾರದು? ಸರಿ, ಅದನ್ನು ಯಶಸ್ವಿಯಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಲು ಸ್ವಲ್ಪ ಟ್ರಿಕಿ ಆಗಿದೆ. ಆದರೆ, ನಾವು ಎರಡು ಸಂಖ್ಯೆಗಳನ್ನು ಹೇಗೆ ಗುಣಿಸಬೇಕೆಂದು ನೀವು ನೆನಪಿಸಿಕೊಂಡರೆ ನಾವು ಇಲ್ಲಿ ಒಂದೇ ತಂತ್ರವನ್ನು ಸುಲಭವಾಗಿ ಬಳಸಬಹುದು.

ಆದ್ದರಿಂದ, ಈ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಕೊಟ್ಟಿರುವ ತಂತಿಗಳಲ್ಲಿ ಒಂದನ್ನು ಬಲದಿಂದ ಎಡಕ್ಕೆ ಸಾಗಿಸುತ್ತೇವೆ. ನಾವು ಸೂಚ್ಯಂಕ ಅಥವಾ ಪಾತ್ರದಲ್ಲಿದ್ದಾಗ, ಈ ಪ್ರಸ್ತುತ ಅಕ್ಷರದೊಂದಿಗೆ ನಾವು ಇತರ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಗುಣಿಸುತ್ತೇವೆ. ನಮ್ಮ ಗುಣಾಕಾರದಿಂದ ನಾವು ಮುಗಿದ ನಂತರ, ನಾವು ಅದರ ಕೊನೆಯಲ್ಲಿ ಸೊನ್ನೆಯನ್ನು ಸೇರಿಸುತ್ತೇವೆ. ಸೇರಿಸಬೇಕಾದ ಸೊನ್ನೆಗಳ ಸಂಖ್ಯೆಯು ಅದರ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿನ ಪ್ರಸ್ತುತ ಅಕ್ಷರಗಳ ಸ್ಥಾನವನ್ನು ಕೊನೆಯಿಂದ ಸಮನಾಗಿರುತ್ತದೆ - 1. ನಾವು ಸೊನ್ನೆಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಮುಗಿದ ನಂತರ, ನಾವು ಈ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಫಲಿತಾಂಶಕ್ಕೆ ಸೇರಿಸುತ್ತೇವೆ. ಆದ್ದರಿಂದ, ನಾವು ಮೊದಲ ಸ್ಟ್ರಿಂಗ್‌ನ ಬಲದಿಂದ ಎಡಕ್ಕೆ ಸಾಗಿದಂತೆ, ಫಲಿತಾಂಶದ ಸ್ಟ್ರಿಂಗ್ ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ.

ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ ಕೋಡ್

ಮಲ್ಟಿಪ್ಲೈ ಸ್ಟ್ರಿಂಗ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಿ ++ ಕೋಡ್

#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

ಮಲ್ಟಿಪ್ಲೈ ಸ್ಟ್ರಿಂಗ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಜಾವಾ ಕೋಡ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ), ಇಲ್ಲಿ N ಮೊದಲ ಸ್ಟ್ರಿಂಗ್‌ನ ಗಾತ್ರ ಮತ್ತು M ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್‌ನ ಗಾತ್ರವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ + ಎಂ), ನಾವು ಫಲಿತಾಂಶವನ್ನು ಪ್ರತ್ಯೇಕ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿರುವುದರಿಂದ ಅದು N + M ಗಾತ್ರವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಹೀಗಾಗಿ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಗುಣಾಕಾರ ತಂತಿಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಆಪ್ಟಿಮೈಸ್ಡ್ ಅಪ್ರೋಚ್

ಆಪ್ಟಿಮೈಸ್ಡ್ ವಿಧಾನವು ಮೊದಲ ಪ್ರಯಾಣದಲ್ಲಿ ಗಮನಿಸಲು ಸ್ವಲ್ಪ ಟ್ರಿಕಿ ಆಗಿದೆ. ಆಪ್ಟಿಮೈಸ್ಡ್ ವಿಧಾನವು ಮೇಲಿನ ವಿವೇಚನಾರಹಿತ ವಿಧಾನದಂತೆಯೇ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆ ಆದರೆ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುವ ಓವರ್ಹೆಡ್ ವೆಚ್ಚವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಮಧ್ಯಂತರ ಫಲಿತಾಂಶದ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಉತ್ತರಕ್ಕೆ ಸೇರಿಸುತ್ತದೆ. ಆಪ್ಟಿಮೈಸ್ಡ್ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಎರಡೂ ತಂತಿಗಳ ಪ್ರತಿಯೊಂದು ಅಂಕೆಗಳನ್ನು ಗುಣಿಸುತ್ತೇವೆ. ಹೀಗಾಗಿ, ನಾವು ಪ್ರತಿಯೊಂದು ಜೋಡಿ ಸೂಚ್ಯಂಕಗಳನ್ನು ಪರಿಗಣಿಸುತ್ತೇವೆ, ಒಂದು ಸೂಚ್ಯಂಕವು ಮೊದಲ ಸ್ಟ್ರಿಂಗ್‌ನಿಂದ ಮತ್ತು ಇನ್ನೊಂದು ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್‌ನಿಂದ. ಸೂಚ್ಯಂಕಗಳು ಕ್ರಮವಾಗಿ ಮೊದಲ ಮತ್ತು ಎರಡನೆಯ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ i, j ಆಗಿದ್ದರೆ, ಅವು ಫಲಿತಾಂಶದ ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿ i + j, i + j + 1 ಸೂಚ್ಯಂಕಗಳನ್ನು ಸಾಧಿಸುತ್ತವೆ. ಆದ್ದರಿಂದ ಈ ಸಂಗತಿಯನ್ನು ಬಳಸಿಕೊಂಡು, ಮಧ್ಯಂತರ ತಂತಿಗಳನ್ನು ಸೇರಿಸುವಲ್ಲಿ, ಸೊನ್ನೆಗಳನ್ನು ಸೇರಿಸುವಲ್ಲಿ, ಪರಿಹಾರವನ್ನು ತೀವ್ರವಾಗಿ ವೇಗಗೊಳಿಸುವ ಮಧ್ಯಂತರ ತಂತಿಗಳನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುವಲ್ಲಿ ಕಳೆದುಹೋಗಿದ್ದ ಓವರ್ಹೆಡ್ ಅನ್ನು ನಾವು ತೆಗೆದುಹಾಕಬಹುದು. ಕೆಳಗಿನ ಚಿತ್ರವನ್ನು ನೋಡುವುದರಿಂದ ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ಉತ್ತಮವಾಗುತ್ತದೆ.

ಸ್ಟ್ರಿಂಗ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಗುಣಿಸಿ

ಆಪ್ಟಿಮೈಸ್ಡ್ ಕೋಡ್

ಮಲ್ಟಿಪ್ಲೈ ಸ್ಟ್ರಿಂಗ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಿ ++ ಕೋಡ್

#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

ಗುಣಾಕಾರ ಸ್ಟ್ರಿಂಗ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಜಾವಾ ಕೋಡ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ), ಸಂಕೀರ್ಣತೆಯು ವಿವೇಚನಾರಹಿತ ವಿಧಾನದಂತೆಯೇ ಇದ್ದರೂ, ಓವರ್ಹೆಡ್ ವೆಚ್ಚಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದು ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ತೀವ್ರವಾಗಿ ಸುಧಾರಿಸುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ + ಎಂ), ಏಕೆಂದರೆ ಫಲಿತಾಂಶದ ಸ್ಟ್ರಿಂಗ್‌ನ ಗಾತ್ರ N + M, ಇಲ್ಲಿ N ಮೊದಲ ಸ್ಟ್ರಿಂಗ್‌ನ ಗಾತ್ರ, ಮತ್ತು M ಎಂಬುದು ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್‌ನ ಗಾತ್ರವಾಗಿದೆ.