געפֿינען ווערטער וואָס קענען זיין געשאפן דורך אותיות Leetcode סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן
מענגע האַשינג

פּראָבלעם דערקלערונג

אין דעם פּראָבלעם "געפֿינען ווערטער וואָס קענען זיין געשאפן דורך אותיות" מיר באַקומען אַ קייט פון סטרינגס וואָס באשטייט פון קליין ענגליש אַלפאַבעץ (ווערטער) און אַ שטריקל וואָס באשטייט פון אַ סכום פון אותיות (טשאַרס).

אונדזער אַרבעט איז צו קאָנטראָלירן פֿאַר יעדער שטריקל אין די מענגע אויב עס קענען זיין געשאפן מיט די אותיות פון טשאַרס (מיר קענען נוצן בלויז איין כאַראַקטער פון טשאַר). אין די סוף, מיר דאַרפֿן צו צוריקקומען די סומע פון ​​די לענג פון אַלע די סטרינגס וואָס קענען זיין געשאפן מיט אותיות פון טשאַרס שטריקל.

בייַשפּיל

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

דערקלערונג:

געפֿינען ווערטער וואָס קענען זיין געשאפן דורך אותיות Leetcode סאַלושאַן

אין דעם בייַשפּיל, מיר קענען פאָרעם העלא און וועלט מיט די אותיות פון די טשאַרס שטריקל. אַזוי די גאַנץ לענג פון העלא און וועלט איז 5 + 5 = 10.

צוגאַנג צו געפֿינען ווערטער וואָס קענען זיין געשאפן דורך אותיות Leetcode סאַלושאַן

צו סאָלווע דעם פּראָבלעם, מיר וועלן נוצן אַ אָפטקייַט מענגע און וואָס וועט קראָם די ציילן פון אותיות אין די שטריקל. מיר וועלן נאָכפאָלגן די סטעפּס צו סאָלווע די פּראָבלעם:

  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

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 * ב) ווייַל מיר זענען דורכגעקאָכט יעדער כאַראַקטער פון אַלע ווערטער. דאָ n איז די לענג פון די געגעבן מענגע און m איז די מאַקסימום לענג פון אַ שטריקל פון געגעבן מענגע.

אָרט קאַמפּלעקסיטי

די פּלאַץ קאַמפּלעקסיטי פון די אויבן קאָד איז אָ (1) ווייַל מיר נוצן בלויז אַ בייַטעוודיק צו קראָם ענטפֿערס.

רעפֿערענצן