Найдите слова, которые могут быть образованы иероглифами Leetcode Solution


Сложный уровень Легко
Часто спрашивают в Амазонка
массив хеширования

Постановка задачи

В задаче «Найти слова, которые могут быть образованы символами» нам дается массив строк, состоящий из строчных английских алфавитов. (слова) и строка который состоит из набора символов (символы).

Наша задача - проверить для каждой строки в массиве, может ли она быть сформирована с использованием символов chars (мы можем использовать каждый символ char только один раз). В конце концов, нам нужно вернуть сумму длин всех строк, которые можно сформировать, используя символы строки chars.

Пример

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

Объяснение:

Найдите слова, которые могут быть образованы иероглифами Leetcode Solution

В этом примере мы можем сформировать hello и world, используя символы строки chars. Таким образом, общая длина hello и world составляет 5 + 5 = 10.

Подход к поиску слов, которые могут быть образованы символами Решение Leetcode

Чтобы решить эту проблему, мы будем использовать частотный массив, который будет хранить количество символов, присутствующих в строке. Мы будем следовать этим шагам, чтобы решить проблему:

  1. Создайте частотный массив и сохраните частоту символов строки символов.
  2. Теперь проверьте каждую строку массива слов одну за другой.
    1. Создайте копию частотного массива.
    2. Теперь проверьте каждый символ выбранной строки. Если частота символа в массиве частот меньше 1, тогда мы не можем сформировать выбранную строку, используя символы строки chars, иначе уменьшите частоту символа на 1.
    3. Если возможно построить строку, используя символы строки символов, тогда добавьте длину выбранной строки в результат.
  3. Вернуть значение результата.

Реализация

Код 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

Сложность времени

Временная сложность приведенного выше кода О (н * м) потому что мы обходим каждый символ всех слов. Здесь n - длина данного массива, а m - максимальная длина строки данного массива.

Пространство сложности

Пространственная сложность приведенного выше кода равна O (1) потому что мы используем только переменную для хранения ответа.

дело