פתרון ה- Leetcode של Word הקצר ביותר


רמת קושי קַל
נשאל לעתים קרובות Google
מפת גיבוב

הבעיה הקצרה ביותר לפתרון Word Leetcode קובעת שקיבלת לוחית רישוי ומערך מחרוזות מערכת הפעלה. עליכם למצוא את המילה הקצרה ביותר להשלמה. מילה מתחרה מוגדרת כמילה שיש בה את כל האלפבית בלוחית הרישוי (חסר רישיות). תדירות האותיות במילה השלמה יכולה להיות גדולה יותר מתדירות האותיות בלוחית הרישוי אך היא לא יכולה להיות פחותה. אז אתה צריך למצוא את המילה הקצרה ביותר להשלמה בין מערך המחרוזות. אז בואו נסתכל על כמה דוגמאות.

פתרון ה- Leetcode של Word הקצר ביותר

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

הסבר: למילה המופיעה בלוחית הרישוי יש 2 שניות ו -1 גר '. המילה מהמערך היא "צעד" שיש בו רק אחד. לפיכך "צעד" אינו מילה השלמה. אבל, "צעדים" כוללים 2 שניות, 1 ט, ואותיות אחרות. המילה "צעדים" מספקת את התנאי להיות מילה השלמה. וזו גם המילה המשלמת הקצרה ביותר. לפיכך, הוא מוחזר כתשובה.

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

הסבר: כל המילים מהמערך הן מילים משלימות. אבל שלוש המילים האחרונות הן המילים המשלמות הקצרות ביותר. מבין המילים המשלמות הקצרות ביותר, אנו מחזירים את המילה השלישית הקצרה ביותר שהיא "מזיק".

גישה לפיתרון Word Leetcode הקצר ביותר

הבעיה פתרון ה- Word Leetcode הקצר ביותר השלים אותנו בבקשה למצוא את המילה הקצרה ביותר. כבר פירטנו מהי מילת השלמה בתיאור הצהרת הבעיה. אז, כדי למצוא את המילה הקצרה ביותר. ראשית, עלינו למצוא את תדירות האותיות על לוחית הרישוי. תדר זה אינו רגיש למקרה של המכתב. ואז אנחנו עוברים מעל מערך של מיתרים. ושוב אנו מבצעים את אותה פעולה של מציאת תדירות האותיות. ואז אנחנו בודקים אם המילה הנוכחית היא מילה משלימה. אם היא וגודל המילה הנוכחית קטן מהמילה הקודמת המשלמת, אנו מעדכנים את התשובה. בסופו של דבר, אנו מחזירים את מילת ההשלמה הקצרה ביותר.

קופונים

קוד 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

קוד Java לפתרון 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 הוא מספר המילים במערך המיתרים. לפיכך לאלגוריתם כולו מורכבות זמן ליניארית.

מורכבות בחלל

O (1), מכיוון שאנו משתמשים בשני HashMaps בגודל קבוע. מורכבות החלל עבור האלגוריתם כולו קבועה.