Count Vowels

Q: מהי סיבוכיות הזמן של ספירת תנועות?

O(n) , כאשר n הוא אורך המחרוזת, כי כל תו נבדק פעם אחת מול לכל היותר חמש אותיות. המקום הנוסף הוא O(1) : מונה אחד והקבוצה הקבועה של התנועות.

Q: האם y היא תנועה בבעיה הזאת?

לא. בכתיב האנגלי, y משמשת לפעמים כתנועה, כמו ב־ rhythm , אבל בבעיות תכנות כמעט תמיד מגדירים את התנועות בתור a , e , i , o ו־ u , וכך גם בבעיה הזאת. אם בעיה כוללת את y , הוסף אותה לאותיות שאתה בודק.

מתחיליםמערכים ומחרוזות

+10

בהינתן מחרוזת s של אותיות באנגלית, החזר את מספר התווים בה שהם תנועות. התנועות הן a, e, i, o ו־u, באותיות קטנות או גדולות. האות y אינה נחשבת.

פונקציה

countVowels(s: string) → integer

sstring: מחרוזת האותיות באנגלית לסריקה
מחזירהinteger: מספר התנועות ב־s, אותיות גדולות וקטנות יחד

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
s מכיל רק אותיות באנגלית (a עד z, A עד Z).

דוגמאות

קלט: s = "Interview"
פלט: 4
הסבר: התנועות הן I, e, i ו־e. האות הגדולה I נחשבת כמו אות קטנה, ולכן התשובה היא 4.

קלט: s = "rhythm"
פלט: 0
הסבר: אין ב־rhythm את a, e, i, o או u, ו־y לא מופיעה ברשימה, לכן התשובה היא 0.

שאלת המשך

האם תוכל להחזיר כמה פעמים כל אחת מחמש התנועות מופיעה, תוך קריאה של המחרוזת פעם אחת בלבד?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

קרא את המחרוזת פעם אחת עם מונה. המר כל תו לאות קטנה, כך שבדיקה אחת מול חמש התנועות תכסה את שני סוגי האותיות.

סופרים כל תנועה במעבר נפרד

האינטואיציה

ספרו כל אחת מעשר האותיות שב-aeiouAEIOU במעבר משלה על המחרוזת, ואז חברו את עשרת הספירות. כל תנועה שווה בדיוק לאחת מעשר האותיות, ולכן היא נספרת פעם אחת, ואף עיצור אינו שווה לאף אחת מהן.

המחרוזת נקראת עשר פעמים. זה עדיין O(n), אבל עבור 5 × 10^4 תווים פירוש הדבר הוא 5 × 10^5 השוואות, כאשר בכל מעבר נקרא כל תו פעם אחת.

אלגוריתם

הגדירו total = 0.
קחו את עשר האותיות aeiouAEIOU אחת בכל פעם.
עבור כל אות, עברו על כל המחרוזת והוסיפו 1 ל־total בכל פעם שתו שווה לה.
לאחר עשרת המעברים, החזירו את total.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

מעבר אחד עם בדיקה של אותיות קטנות

האינטואיציה

קרא את המחרוזת פעם אחת ובדוק עבור כל תו אם הוא תנועה. המרתה לאותיות קטנות תחילה הופכת את I ל־i ומשאירה עיצורים כעיצורים, כך שמשווים לחמש אותיות במקום לעשר.

הבדיקה מתבצעת בזמן קבוע: באמצעות switch, חיפוש בקבוצה או חיפוש במחרוזת aeiou. כל תו נקרא פעם אחת ונשמר רק מונה: זמן O(n), מקום O(1).

אלגוריתם

הגדר את count = 0.
עבור על המחרוזת תו אחד בכל פעם.
המר את התו לאות קטנה.
אם הוא a, e, i, o או u, הוסף 1 ל-count.
החזר את count.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

מלכודות ומקרי קצה

בדיקה של אותיות קטנות בלבד. השוואה ל־aeiou בלבד מפספסת את האות הגדולה I במילה Interview ומחזירה 3.
ספירת y. כאן היא אף פעם אינה תנועה, ולכן rhythm מחזירה 0.
התייחסות לאינדקס 0 כאילו אין התאמה. "aeiou".indexOf('a') הוא 0, וזה מציין התאמה. בדקו אם הערך הוא -1, או ב־PHP השוו את strpos ל־false באמצעות !==, כי שם 0 == false.
קריאה ל־strlen(s) בתנאי הלולאה ב־C. היא סורקת מחדש את המחרוזת בכל צעד, ולכן עיבוד של 5 × 10^4 תווים דורש בערך 2.5 × 10^9 צעדים.

שאלות נפוצות3

איך סופרים את התנועות במחרוזת?

עבור על המחרוזת פעם אחת באמצעות מונה. המר כל תו לאות קטנה והוסף 1 אם הוא a, e, i, o או u. כשהלולאה מסתיימת, המונה מכיל את התשובה.

מהי סיבוכיות הזמן של ספירת תנועות?

O(n), כאשר n הוא אורך המחרוזת, כי כל תו נבדק פעם אחת מול לכל היותר חמש אותיות. המקום הנוסף הוא O(1): מונה אחד והקבוצה הקבועה של התנועות.

האם y היא תנועה בבעיה הזאת?

לא. בכתיב האנגלי, y משמשת לפעמים כתנועה, כמו ב־rhythm, אבל בבעיות תכנות כמעט תמיד מגדירים את התנועות בתור a, e, i, o ו־u, וכך גם בבעיה הזאת. אם בעיה כוללת את y, הוסף אותה לאותיות שאתה בודק.

def countVowels(s):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנט

s = "Interview"

הפלט הצפוי