Калимаҳоеро ёбед, ки аз рӯи аломатҳои Leetcode Solution сохта шаванд  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon
алгоритмҳо тартиботи ҳарбӣ рамзгузорӣ Хашм мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions

Изҳороти мушкилот  

Дар масъалаи "Калимаҳоеро пайдо кунед, ки бо аломатҳо сохта мешаванд" ба мо як қатор сатрҳо дода мешаванд, ки аз алифбои хурди англисӣ иборатанд (калимаҳо) ва данд ки аз маҷмӯи аломатҳо иборат аст (чарсҳо).

Вазифаи мо аз он иборат аст, ки ҳар як сатрро дар массив тафтиш кунем, агар он бо ёрии аломатҳои чархҳо сохта шавад (мо ҳар як аломати char-ро танҳо як маротиба истифода бурда метавонем). Дар ниҳоят, мо бояд маблағи дарозии ҳамаи сатрҳоро, ки бо истифодаи аломатҳои сатри чархҳо сохта мешаванд, баргардонем.

мисол

words = ["hello","world","tutorialcup"], chars = "welldonehoneyr"
10

Шарҳ:

Калимаҳоеро ёбед, ки аз рӯи аломатҳои Leetcode Solution сохта шавандпайвандак

Дар ин мисол, мо метавонем бо истифода аз аломатҳои сатри чарсҳо салом ва ҷаҳон созем. Ҳамин тавр, дарозии умумии салом ва ҷаҳон 5 + 5 = 10 мебошад.

Усули дарёфти калимаҳое, ки тавассути аломатҳои Leetcode Solution сохта мешаванд  

Барои ҳалли ин масъала мо массиви басомадро истифода мебарем ва шумораи аломатҳои дар сатр мавҷудбударо нигоҳ медорем. Мо барои ҳалли мушкил ин амалҳоро иҷро хоҳем кард:

  1. Массиви басомадро созед ва басомади аломатҳои сатри чархҳоро нигоҳ доред.
  2. Ҳоло ҳар як сатри калимаи массивро як ба як санҷед.
    1. Нусхаи массиви басомадро эҷод кунед.
    2. Акнун ҳар як аломати сатри интихобшударо санҷед. Агар басомади аломат дар массиви басомад камтар аз 1 бошад, мо сатри интихобшударо бо истифодаи аломатҳои сатри чархҳо ташкил карда наметавонем, агар басомади аломатҳоро 1 кам кунем.
    3. Агар сатрро бо истифодаи аломатҳои сатри чархҳо сохтан имконпазир бошад, пас дарозии сатри интихобшударо ба натиҷа илова кунед.
  3. Арзиши натиҷаро баргардонед.
ҳамчунин нигаред
Баргардонидани унсурҳои якуми K навбат

татбиќи

Коди C ++ барои ёфтани калимаҳое, ки бо аломатҳо сохта мешаванд

#include <bits/stdc++.h> 
using namespace std; 
int countCharacters(vector<string>& words, string chars) {
  vector<int> cnt(26);
  int res = 0;
  for (auto ch : chars) ++cnt[ch - 'a'];
  for (auto w : words) {
    vector<int> cnt1 = cnt;
    bool match = true;
    for (auto ch : w) {
      if (--cnt1[ch - 'a'] < 0) {
        match = false;
        break;
      }
    }
    if (match) res += w.size();
  }
  return res;
}

int main() 
{ 
    vector<string> words {"hello","world","tutorialcup"};
    string ch="welldonehoneyr";
    int ans=countCharacters(words,ch); 
    cout<<ans<<endl;
    return 0;
}
10

Рамзи Java барои Калимаҳоеро ёбед, ки бо аломатҳо сохта мешаванд

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
public static int countCharacters(String[] words, String chars) {
        int[] count = new int[26];
        int res = 0;
        
        for (char ch : chars.toCharArray()) {
            count[ch - 'a']++;
        }
        
        for (String word : words) {
            int[] temp = count.clone();
            boolean match = true;
            
            for (char ch : word.toCharArray()) {
                if (--temp[ch - 'a'] < 0) {
                    match = false;
                    break;
                }
            }
            
            if (match) {
                res += word.length();
            }
        }
        
        return res;
    }
  public static void main(String[] args) {
        String[] words={"hello","world","tutorialcup"};
        String ch="welldonehoneyr";
        int ans=countCharacters(words,ch); 
        System.out.println(ans);
  }
}
10

Таҳлили мураккаби калимаҳое, ки тавассути аломатҳои Leetcode Solution сохта мешаванд, пайдо кунед  

Мураккабии вақт

Мураккабии вақти рамзи боло дар он аст О (н * м) зеро мо ҳар як хислати ҳама калимаҳоро тай карда истодаем. Дар ин ҷо n дарозии массиви додашуда ва m дарозии максималии сатри массиви додашуда мебошад.

Мураккабии фазо

Мураккабии фазоии рамзи дар боло зикршуда О (1) зеро мо барои тағир додани ҷавоб танҳо як тағирёбандаро истифода мебарем.

Адабиёт