اسٹرنگز لیٹکوڈ حل کو ضرب دیں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون ایپل ByteDance Expedia فیس بک گوگل Houzz ریاضی مائیکروسافٹ اوریکل چوک ٹویٹر Uber Zillow
ریاضی سلک

مسئلہ ضرب المثل اسٹرنگز لیٹکوڈ حل ہمیں دو ڈوروں کو ضرب دینے کے لئے کہتا ہے جو ہمیں ان پٹ کے بطور دیئے جاتے ہیں۔ ہمیں کالر فنکشن میں ضرب لگانے کے اس نتیجے کو پرنٹ کرنے یا واپس کرنے کی ضرورت ہے۔ لہذا اس کو مزید باضابطہ طور پر دو ڈور ڈالنے کے ل the ، دیئے گئے تاروں کی مصنوعات تلاش کریں۔ یہ ڈور بہت سے ہندسے ہوسکتے ہیں۔ لہذا ، کسی کو دیئے گئے تاروں کو محض عدد میں تبدیل کرنے کی کوشش نہیں کرنی چاہئے اور پھر سادہ ضرب استعمال کرنا چاہئے۔ آئیے بہتر تفہیم کے لئے کچھ مثالوں پر ایک نظر ڈالیں۔

مثال کے طور پر

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

وضاحت: چونکہ دونوں تاروں کے صرف ایک ہندسے ہیں۔ ہم چیک کرسکتے ہیں کہ آؤٹ پٹ 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"

وضاحت: اب ، اس مثال میں ، ہمیں دو ڈور دیئے گئے ہیں جو ایک بڑی تار کو آؤٹ پٹ دینے کے لئے ضرب دیئے گئے ہیں جو اعداد و شمار کی ایک قسم میں محفوظ نہیں ہوسکتے ہیں۔ لہذا ، یہ مثال ان چند لوگوں میں سے ایک ہے جو ہمارے الگورتھم سے نمٹنے کے قابل ہونا چاہئے۔

ضرب اسٹرنگز لیٹکوڈ حل کے لئے بروٹ فورس اپروچ

مسئلہ ضرب المثل اسٹرنگز لیٹکوڈ حل نے ہم سے صرف دو دیئے گئے تاروں کو ضرب کرنے کو کہا۔ تو ، کیوں ہم صرف ایسا نہیں کرتے؟ ٹھیک ہے ، اس کو کامیابی کے ساتھ نافذ کرنا قدرے مشکل ہے۔ لیکن ، اگر آپ کو یاد ہے کہ ہم کس طرح دو نمبروں کو ضرب دیتے تھے تو ہم یہاں آسانی سے ایک ہی تکنیک استعمال کرسکتے ہیں۔

لہذا ، اس نقطہ نظر میں ، ہم دائیں سے بائیں دیئے گئے ایک تاروں کو عبور کریں گے۔ جب ہم کسی اشاریہ یا کسی کردار میں ہوتے ہیں ، تو ہم موجودہ سارے کردار کو دوسرے سٹرنگ میں ضرب دیتے ہیں۔ ایک بار جب ہم اپنی ضرب کے ساتھ کام کرجائیں گے ، تو ہم اس کے آخر میں زیروز شامل کردیں گے۔ زیرو کی تعداد جو شامل کی جانی چاہئے اس کے تار میں موجودہ حرف کی حیثیت اختتام سے برابر ہوتی ہے۔ 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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N * M)، جہاں N پہلی تار کا حجم ہے اور M دوسری تار کا حجم ہے۔

خلائی پیچیدگی

O (N + M) ، چونکہ ہم نے نتیجہ کو ایک الگ تار میں اسٹور کیا ہے جس میں N + M کا سائز ہوسکتا ہے۔ اس طرح خلائی پیچیدگی لکیری ہے۔

ضرب المثل اسٹرکس لیٹکوڈ حل کے ل Op آپٹائزڈ اپروچ

پہلی مرتبہ مشاہدہ کرنے کے لئے اصلاح شدہ نقطہ نظر قدرے مشکل ہے۔ مذکورہ بالا نقطہ نظر میں بھی اسی طرح کی پیچیدگی ہوتی ہے جیسا کہ مذکورہ بالا قوت نقطہ نظر کی طرح ہوتا ہے لیکن اس میں تار کو تبدیل کرنے کے اوور ہیڈ لاگت اور جواب میں ہر انٹرمیڈیٹ کے نتیجے میں سٹرنگ کو شامل کرنے کو ختم کردیا جاتا ہے۔ مرضی کے نقطہ نظر میں ، ہم دونوں تار کے ہر ہندسے کو ضرب دیتے ہیں۔ اس طرح ، ہم ہر ایک جوڑے کے اشارے پر غور کرتے ہیں ، ایک اشارے پہلے تار سے اور دوسرا دوسرے تار سے۔ خیال یہ ہے کہ اگر انڈیکس بالترتیب پہلی اور دوسری تار میں 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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N * M)، اگرچہ پیچیدگی طاقتور طریقہ کے مترادف ہے ، لیکن ہیڈ لاگت کو دور کرنے سے کارکردگی میں تیزی سے بہتری آتی ہے۔

خلائی پیچیدگی

O (N + M) ، کیونکہ نتیجہ والے تار کا حجم N + M ہے ، جہاں N پہلی تار کا حجم ہے ، اور M دوسری تار کا حجم ہے۔