అక్షరాల లీట్‌కోడ్ సొల్యూషన్ ద్వారా రూపొందించగల పదాలను కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్
అర్రే హ్యాషింగ్

సమస్యల నివేదిక

“అక్షరాలచే రూపొందించబడిన పదాలను కనుగొనండి” అనే సమస్యలో మనకు లోయర్ కేస్ ఇంగ్లీష్ అక్షరాలతో కూడిన తీగలను ఇస్తారు. (పదాలు) మరియు ఒక స్ట్రింగ్ ఇది అక్షరాల సమితిని కలిగి ఉంటుంది (అక్షరాలు).

అక్షరాల అక్షరాలను ఉపయోగించి ఏర్పడగలిగితే శ్రేణిలోని ప్రతి స్ట్రింగ్ కోసం తనిఖీ చేయడం మా పని (మేము చార్ యొక్క ప్రతి అక్షరాన్ని ఒక్కసారి మాత్రమే ఉపయోగించవచ్చు). చివరికి, అక్షరాల స్ట్రింగ్ యొక్క అక్షరాలను ఉపయోగించి ఏర్పడే అన్ని తీగల పొడవు యొక్క మొత్తాన్ని మనం తిరిగి ఇవ్వాలి.

ఉదాహరణ

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

వివరణ:

అక్షరాల లీట్‌కోడ్ సొల్యూషన్ ద్వారా రూపొందించగల పదాలను కనుగొనండి

ఈ ఉదాహరణలో, అక్షరాల స్ట్రింగ్ యొక్క అక్షరాలను ఉపయోగించి మేము హలో మరియు ప్రపంచాన్ని ఏర్పరుస్తాము. కాబట్టి హలో మరియు ప్రపంచం యొక్క మొత్తం పొడవు 5 + 5 = 10.

అక్షరాల లీట్‌కోడ్ సొల్యూషన్ ద్వారా రూపొందించగల పదాలను కనుగొనడానికి విధానం

ఈ సమస్యను పరిష్కరించడానికి మేము ఫ్రీక్వెన్సీ శ్రేణిని ఉపయోగిస్తాము మరియు అది స్ట్రింగ్‌లో ఉన్న అక్షరాల సంఖ్యను నిల్వ చేస్తుంది. సమస్యను పరిష్కరించడానికి మేము ఈ దశలను అనుసరిస్తాము:

  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

అక్షరాల లీట్‌కోడ్ సొల్యూషన్ ద్వారా రూపొందించబడే పదాలను కనుగొనే సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై కోడ్ యొక్క సమయం సంక్లిష్టత O (n * m) ఎందుకంటే మేము అన్ని పదాల యొక్క ప్రతి పాత్రను దాటుతున్నాము. ఇక్కడ n అనేది ఇచ్చిన శ్రేణి యొక్క పొడవు మరియు m ఇచ్చిన శ్రేణి యొక్క స్ట్రింగ్ యొక్క గరిష్ట పొడవు.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత O (1) ఎందుకంటే మేము జవాబును నిల్వ చేయడానికి వేరియబుల్ మాత్రమే ఉపయోగిస్తున్నాము.

ప్రస్తావనలు