מצא מילים שיכולות להיווצר על ידי תווים פתרון Leetcode


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית
מערך חבטות

הצהרת בעיה

בבעיה "מצא מילים שיכולות להיווצר על ידי דמויות" אנו מקבלים מערך מחרוזות המורכב מאלפביתים קטנים באנגלית. (מילים) וכן מחרוזת שמורכב ממערכת דמויות (צ'ארס).

המשימה שלנו היא לבדוק כל מחרוזת במערך אם ניתן ליצור אותה באמצעות תווים של תווים (אנו יכולים להשתמש בכל תו של char רק פעם אחת). בסופו של דבר, עלינו להחזיר את סכום האורך של כל המיתרים שניתן ליצור בעזרת תווים של מחרוזת התווים.

דוגמה

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

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n * m) כי אנחנו חוצים כל דמות מכל המילים. כאן n הוא אורך המערך הנתון ו- m הוא האורך המרבי של מחרוזת של מערך נתון.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (1) מכיוון שאנחנו משתמשים רק במשתנה לאחסון התשובה.

הפניות