שאָרטיסט קאַמפּליטינג וואָרט לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין גוגל
האַשמאַפּ

די פּראָבלעם שאָרטיסט קאַמפּליטינג וואָרט לעעטקאָדע סאַלושאַן שטאַטן אַז איר האָבן אַ דערלויבעניש טעלער און אַ פּלאַץ פון אַס סטרינגס. איר דאַרפֿן צו געפֿינען די שאָרטיסט קאַמפּליטינג וואָרט. א קאָנקורענט וואָרט איז דיפיינד ווי אַ וואָרט וואָס האט אַלע די אַלפאַבעץ אין די דערלויבעניש טעלער (פאַל ינסענסיטיוו). די אָפטקייַט פון אותיות אין קאַמפּליטינג וואָרט קענען זיין גרעסער ווי די אָפטקייַט פון אותיות אין די דערלויבעניש טעלער, אָבער עס קען נישט זיין ווייניקער. אַזוי, איר דאַרפֿן צו געפֿינען די שאָרטיסט קאַמפּליטינג וואָרט צווישן די שטריקל שטריקל. לאָמיר נעמען עטלעכע ביישפילן.

שאָרטיסט קאַמפּליטינג וואָרט לעעטקאָדע סאַלושאַן

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

דערקלערונג: די וואָרט אין די דערלויבעניש טעלער האט 2 s און 1 ה. די וואָרט פון די מענגע איז "שריט" וואָס האט בלויז אַ איין. אזוי "שריט" איז נישט אַ קאַמפּליטינג וואָרט. אָבער, "סטעפּס" האט 2 s, 1 ה און אנדערע אותיות. די וואָרט "טריט" סאַטיספייז די באדינגונג צו זיין אַ קאַמפּליטינג וואָרט. און דאָס איז אויך די שאָרטיסט קאַמפּליטינג וואָרט. אזוי, עס איז אומגעקערט ווי אַן ענטפער.

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

דערקלערונג: כל די ווערטער פון די מענגע זענען קאַמפּליטינג ווערטער. אָבער די לעצטע 3 ווערטער זענען די שאָרטיסט קאַמפּליטינג ווערטער. צווישן די שאָרטיסט קאַמפּליטינג ווערטער, מיר קערט דער ערשטער שאָרטיסט קאַמפּליטינג וואָרט וואָס איז "פּעסט".

צוגאַנג פֿאַר שאָרטיסט קאַמפּליטינג וואָרט לעעטקאָדע סאַלושאַן

די פּראָבלעם שאָרטיסט קאַמפּליטינג וואָרט לעעטקאָדע סאַלושאַן געבעטן אונדז צו געפֿינען די שאָרטיסט קאַמפּליטינג וואָרט. מיר האָבן שוין ספּעציפיצירט וואָס אַ קאַמפּליטינג וואָרט איז אין די באַשרייַבונג פון די פּראָבלעם ויסזאָגונג. אַזוי, צו געפֿינען די שאָרטיסט קאַמפּליטינג וואָרט. ערשטער, מיר מוזן געפֿינען די אָפטקייַט פון די אותיות אויף די דערלויבעניש טעלער. די אָפטקייַט איז ינסענסיטיוו צו דעם בריוו. דערנאָך מיר אַריבער די מענגע פון סטרינגס. און ווידער מיר דורכפירן די זעלבע אָפּעראַציע צו געפֿינען די אָפטקייַט פון אותיות. דערנאָך מיר קאָנטראָלירן אויב די קראַנט וואָרט איז אַ קאַמפּליטינג וואָרט. אויב עס איז און די גרייס פון דעם קראַנט וואָרט איז קלענערער ווי די פֿריִערדיקע קאַמפּליטינג וואָרט, מיר דערהייַנטיקן די ענטפער. אין די סוף, מיר צוריקקומען די שאָרטיסט קאַמפּליטינג וואָרט.

קאָדעקס

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

Java קאָד פֿאַר שאָרטיסט קאָמפּלעטינג וואָרט לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), וווּ N איז די נומער פון ווערטער אין די שטריקל שטריקל. אזוי די גאנצע אַלגערידאַם האט לינעאַר צייט קאַמפּלעקסיטי.

ספעיס קאַמפּלעקסיטי

אָ (1), זינט מיר נוצן צוויי HashMaps פון קעסיידערדיק גרייס. די פּלאַץ קאַמפּלעקסיטי פֿאַר די גאנצע אַלגערידאַם איז קעסיידערדיק.