Пронајдете зборови што можат да бидат формирани од ликови Решение за код


Ниво на тешкотија Лесно
Често прашувано во Амазон
Низа Хашинг

Проблем изјава

Во проблемот „Пронајди зборови што можат да бидат формирани од знаци“ ни се дава низа низи кои се состојат од англиски букви со мали букви (зборови) и низа што се состои од збир на карактери (карактери).

Нашата задача е да провериме за секоја низа во низата дали може да се формира со употреба на знаци на карактери (можеме да го користиме секој карактер на јаглен само еднаш). На крајот, треба да го вратиме збирот на должината на сите жици што можат да се формираат со употреба на карактери на карактери.

пример

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

објаснување:

Пронајдете зборови што можат да бидат формирани од ликови Решение за код

Во овој пример, можеме да формираме здраво и свет користејќи ги ликовите од жицата со знаци. Значи, вкупната должина на здраво и свет е 5 + 5 = 10.

Пристап кон пронаоѓање зборови што можат да се формираат со решение за ликови со знаци

За да го решиме овој проблем, ќе користиме низа на фреквенции и таа ќе го зачува бројот на знаци присутни во низата. Willе ги следиме овие чекори за да го решиме проблемот:

  1. Создадете низа на фреквенции и зачувајте ја фреквенцијата на знаците на низата со знаци.
  2. Сега проверете ја секоја низа од низа зборови еден по еден.
    1. Создадете копија од низата фреквенција.
    2. Сега проверете го секој знак од избраната низа. Ако фреквенцијата на еден карактер во низата на фреквенција е помала од 1, тогаш не можеме да формираме избрана низа користејќи ги знаците на низата за знаци на друга, да ја намалиме фреквенцијата на карактерот за 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

Јава код за пронаоѓање зборови што можат да бидат формирани од знаци

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

Анализа на сложеност за пронаоѓање зборови што можат да се формираат со решение за ликови со знаци

Временска сложеност

Временската сложеност на горенаведениот код е О (н * м) затоа што го минуваме секој карактер од сите зборови. Тука n е должината на дадената низа и m е максималната должина на низата од дадената низа.

Комплексноста на просторот

Комплексноста на просторот на горенаведениот код е О (1) затоа што користиме само променлива за складирање на одговор.

Референци