最短的完成Word Leetcode解決方案


難度級別 容易獎學金
經常問 谷歌
哈希圖

最短補全單詞Leetcode解決方案問題指出,您將獲得一個牌照和一系列os字符串。 您需要找到最短的補全單詞。 競爭詞定義為在車牌中具有所有字母的詞(不區分大小寫)。 完整單詞中字母的頻率可以大於車牌中字母的頻率,但不能小於。 因此,您需要在字符串數組中找到最短的補全單詞。 因此,讓我們看一些示例。

最短的完成Word Leetcode解決方案

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

說明:車牌上的單詞為2 s和1 t。 數組中的單詞是“ step”,它只有一個。 因此,“步驟”並不是一個完整的詞。 但是,“ steps”有2 s,1 t和其他字母。 單詞“ steps”滿足作為完整單詞的條件。 它也是最短的補全詞。 因此,將其作為答案返回。

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

說明:數組中的所有單詞都是完整單詞。 但是最後三個詞是最短的補全詞。 在最短補全詞中,我們返回第一個最短補全詞“害蟲”。

最短的完成Word Leetcode解決方案的方法

最短補全單詞Leetcode解決方案問題要求我們找到最短補全單詞。 我們已經在問題說明的描述中指定了完整的單詞。 因此,要找到最短的補全字。 首先,我們必須找到車牌上字母的頻率。 該頻率對字母的大小寫不敏感。 然後我們遍歷 排列 的字符串。 再一次,我們執行查找字母頻率的相同操作。 然後,我們檢查當前單詞是否為完整單詞。 如果是,並且當前單詞的大小小於上一個完整單詞的大小,我們將更新答案。 最後,我們返回最短的補全單詞。

推薦碼

最短補全Word Leetcode解決方案的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

最短補全Word Leetcode解決方案的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是字符串數組中的單詞數。 因此,整個算法具有線性時間複雜度。

空間複雜度

O(1), 因為我們使用了兩個恆定大小的HashMaps。 整個算法的空間複雜度是恆定的。