أقصر حل لاستكمال Word Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في جوجل
خريطة التجزئة

تنص مشكلة أقصر إكمال Word Leetcode Solution على حصولك على لوحة ترخيص ومجموعة من سلاسل نظام التشغيل. أنت بحاجة إلى العثور على أقصر كلمة مكتملة. يتم تعريف الكلمة المنافسة على أنها الكلمة التي تحتوي على جميع الحروف الهجائية في لوحة الترخيص (غير حساسة لحالة الأحرف). يمكن أن يكون تكرار الأحرف في إكمال الكلمة أكبر من تكرار الأحرف في لوحة الترخيص ولكن لا يمكن أن يكون أقل. لذلك ، أنت بحاجة إلى العثور على أقصر كلمة مكتملة بين مجموعة السلاسل النصية. لذا ، دعونا نلقي نظرة على بعض الأمثلة.

أقصر حل لاستكمال Word Leetcode

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

شرح: الكلمة الواردة في لوحة الترخيص لها 2 ثانية و 1 طن. الكلمة من المصفوفة هي "خطوة" التي تحتوي على واحدة فقط. وبالتالي فإن "الخطوة" ليست كلمة مكتملة. لكن تحتوي "الخطوات" على 2 s و 1 t وحروف أخرى. كلمة "خطوات" تفي بشرط أن تكون كلمة مكتملة. وهي أيضًا أقصر كلمة مكتملة. وبالتالي ، يتم إرجاعها كإجابة.

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

شرح: كل الكلمات من المصفوفة هي كلمات مكتملة. لكن الكلمات الثلاث الأخيرة هي أقصر كلمات مكتملة. من بين أقصر الكلمات المكتملة ، نعيد أول كلمة مكتملة هي "الآفات".

نهج لأقصر حل لاستكمال Word Leetcode

طلبت منا مشكلة أقصر إكمال Word Leetcode Solution العثور على أقصر كلمة مكتملة. لقد حددنا بالفعل ما هي الكلمة المكتملة ، في وصف بيان المشكلة. لذلك ، للعثور على أقصر كلمة مكتملة. أولاً ، علينا إيجاد تواتر الحروف على لوحة الترخيص. هذا التردد غير حساس لحالة الرسالة. ثم ننتقل فوق مجموعة من السلاسل. ومرة أخرى نقوم بنفس العملية لإيجاد تردد الحروف. ثم نتحقق مما إذا كانت الكلمة الحالية هي كلمة مكتملة. إذا كان الأمر كذلك وكان حجم الكلمة الحالية أصغر من الكلمة المكتملة السابقة ، فإننا نقوم بتحديث الإجابة. في النهاية ، نعيد أقصر كلمة مكتملة.

رمز

كود C ++ لأقصر حل لاستكمال Word Leetcode

#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

كود جافا لأقصر حل لاستكمال Word Leetcode

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 هو عدد الكلمات في مصفوفة السلاسل النصية. وبالتالي فإن الخوارزمية بأكملها لها تعقيد زمني خطي.

تعقيد الفضاء

يا (1) ، نظرًا لأننا نستخدم خريطتي HashMap بحجم ثابت. التعقيد المكاني للخوارزمية بأكملها ثابت.