최단 완성 워드 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 구글
알고리즘 코딩 해시맵 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 34

Shortest Completing Word Leetcode Solution 문제는 번호판과 os 문자열 배열이 주어 졌다고 말합니다. 가장 짧은 완성 단어를 찾아야합니다. 경쟁 단어는 번호판에 모든 알파벳이 포함 된 단어로 정의됩니다 (대소 문자 구분 안 함). 완성 된 단어의 글자 빈도는 번호판의 글자 빈도보다 클 수 있지만 그보다 적을 수는 없습니다. 따라서 문자열 배열 중에서 가장 짧은 완성 단어를 찾아야합니다. 자, 몇 가지 예를 살펴 보겠습니다.

최단 완성 워드 Leetcode 솔루션

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

설명 : 번호판에 표시된 단어는 2 초와 1 티입니다. 배열의 단어는 단 하나만있는 "단계"입니다. 따라서“단계”는 완전한 단어가 아닙니다. 그러나 "steps"에는 2 s, 1 t 및 기타 문자가 있습니다. “단계”라는 단어는 완전한 단어라는 조건을 충족시킵니다. 그리고 그것은 또한 가장 짧은 완성 단어입니다. 따라서 답변으로 반환됩니다.

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

설명 : 배열의 모든 단어가 단어를 완성하고 있습니다. 그러나 마지막 3 개 단어는 가장 짧은 완성 단어입니다. 가장 짧은 완성 단어 중 가장 짧은 완성 단어 인“pest”를 반환합니다.

최단 완성 워드 Leetcode 솔루션에 대한 접근 방식

Shortest Completing Word Leetcode Solution 문제는 우리에게 가장 짧은 완성 단어를 찾도록 요청했습니다. 우리는 이미 문제 설명에 완전한 단어가 무엇인지 명시했습니다. 그래서, 가장 짧은 완성 단어를 찾으려면. 먼저 번호판에있는 글자의 빈도를 찾아야합니다. 이 빈도는 문자의 대소 문자를 구분하지 않습니다. 그런 다음 우리는 정렬 문자열 그리고 다시 한번 우리는 글자의 빈도를 찾는 동일한 작업을 수행합니다. 그런 다음 현재 단어가 완성 단어인지 확인합니다. 현재 단어의 크기가 이전 완성 단어보다 작 으면 답변을 업데이트합니다. 결국 가장 짧은 완성 단어를 반환합니다.

암호

최단 완성 워드 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

최단 완성 워드 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

복잡성 분석

시간 복잡성

의 위에), 여기서 N은 문자열 배열의 단어 수입니다. 따라서 전체 알고리즘은 선형 시간 복잡도를 갖습니다.

공간 복잡성

O (1), 크기가 일정한 두 개의 HashMap을 사용하기 때문입니다. 전체 알고리즘의 공간 복잡도는 일정합니다.

코멘트를 남겨

Translate »
1