کم سے کم مکمل کلام لیٹ کوڈ حل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے گوگل
ہش میپ

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

کم سے کم مکمل کلام لیٹ کوڈ حل

licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
"steps"

وضاحت: لائسنس پلیٹ میں دیئے گئے لفظ میں 2 s اور 1 t ہے۔ صف کا لفظ "قدم" ہے جس میں صرف ایک ہی لفظ ہے۔ اس طرح "قدم" ایک مکمل لفظ نہیں ہے۔ لیکن ، "اقدامات" میں 2 s ، 1 t ، اور دوسرے حروف ہیں۔ لفظ "اقدامات" ایک مکمل لفظ ہونے کی شرط کو پورا کرتا ہے۔ اور یہ مختصر ترین لفظ بھی ہے۔ اس طرح ، یہ جواب کے طور پر واپس آ گیا ہے۔

licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
"pest"

وضاحت: صف سے تمام الفاظ الفاظ مکمل کر رہے ہیں۔ لیکن آخری 3 الفاظ مختصر ترین الفاظ ہیں۔ مختصر ترین الفاظ کو ختم کرنے میں ، ہم سب سے کم مختصر الفاظ کو واپس کرتے ہیں جو "کیڑے" ہے۔

کم سے کم مکمل کلام لیٹ کوڈ حل کے ل Appro نقطہ نظر

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

ضابطے

کم سے کم مکمل کلام لیٹ کوڈ حل کے لئے C ++ کوڈ

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

string shortestCompletingWord(string licensePlate, vector<string>& words) {
    unordered_map<char, int> m;
    for(auto x: licensePlate){
        if((x>='A' && x<='Z') || (x>='a' && x<='z'))
            m[tolower(x)]++;
    }
    string answer = string(16, 'a');
    for(auto word: words){
        unordered_map<char, int> mm;
        for(auto x: word){
            if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                mm[tolower(x)]++;
        }
        bool cant = false;
        for(char i='a';i<='z';i++)
            if(mm[i] < m[i])
                cant = true;
        if(!cant){
            if(word.length() < answer.length())
                answer = word;
        }
    }
    return answer;
}

int main(){
    string licensePlate = "1s3 PSt";
    vector<string> words({"step","steps","stripe","stepple"});
    cout<<shortestCompletingWord(licensePlate, words);
}
steps

کم سے کم مکمل کلام لیٹ کوڈ حل کے لئے جاوا کوڈ

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

class Main
{
  public static String shortestCompletingWord(String licensePlate, String[] words) {
       HashMap <Character, Integer> m = new HashMap<Character, Integer>();
        int licensePlateSize = licensePlate.length();
        for(int i=0;i<licensePlateSize;i++){
            char x = licensePlate.charAt(i);
            if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                m.put(Character.toLowerCase(x), m.containsKey(Character.toLowerCase(x)) ? (m.get(Character.toLowerCase(x)) + 1) : 1);
        }
        String answer = "aaaaaaaaaaaaaaaa";
        for(String word: words){
            HashMap<Character, Integer> mm = new HashMap<Character, Integer>();
            int wordSize = word.length();
            for(int i=0;i<wordSize;i++){
                char x = word.charAt(i);
                if((x>='A' && x<='Z') || (x>='a' && x<='z'))
                    mm.put(Character.toLowerCase(x), mm.containsKey(Character.toLowerCase(x)) ? (mm.get(Character.toLowerCase(x)) + 1) : 1);
            }
            boolean cant = false;
            for(char i='a';i<='z';i++){
                int a = m.containsKey(i) ? m.get(i) : 0;
                int b = mm.containsKey(i) ? mm.get(i) : 0;
                if(b < a)
                    cant = true;
            }
            if(cant == false){
                if(word.length() < answer.length())
                    answer = word;
            }
        }
        return answer; 
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String licensePlate = "1s3 PSt";
      String words[] = {"step","steps","stripe","stepple"};
      System.out.print(shortestCompletingWord(licensePlate, words));
  }
}
steps

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

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

O (N) ، جہاں N تار کے صف میں الفاظ کی تعداد ہے۔ اس طرح پوری الگورتھم میں وقتی پیچیدگی ہوتی ہے۔

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

O (1) ، چونکہ ہم مستحکم سائز کے دو ہش میپ استعمال کرتے ہیں۔ پورے الگورتھم کے لئے جگہ کی پیچیدگی مستقل ہے۔