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.

+18 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

האינטואיציה

פרקו את השאלה לעשר שאלות קטנות יותר: כמה אותיות a יש, כמה אותיות e, וכך הלאה עד U. כל אחת מהן היא ספירה פשוטה. עברו על המחרוזת והוסיפו 1 בכל פעם שהתווים שווה לאות שאתם מחפשים, ואז חברו את עשר הספירות.

כל תנועה ב-s שווה בדיוק לאחת מעשר האותיות שב-aeiouAEIOU, ולכן היא נספרת בדיוק פעם אחת, ואף עיצור אינו שווה לאף אחת מהן. עבור Interview, המעבר עבור e מוצא 2, המעבר עבור i מוצא 1, המעבר עבור I מוצא 1, ובשבעת המעברים האחרים לא נמצא דבר: 4 בסך הכול.

המחרוזת נקראת עשר פעמים, כלומר בערך 10n השוואות. זה עדיין 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 ו-E הופכת ל-e, בעוד שעיצורים נשארים עיצורים, כך שעליכם להשוות רק לחמש האותיות a, e, i, o ו-u.

הבדיקה מתבצעת בזמן קבוע: באמצעות switch על פני חמש אותיות, חיפוש בקבוצה או חיפוש במחרוזת בת חמש האותיות aeiou. בסריקת Interview, המונה עולה ב-I, e, i ו-e, ומסתיים ב-4.

כל תו נקרא פעם אחת, ולכן זמן הריצה הוא 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. בבעיה הזו y לעולם אינה תנועה, ולכן rhythm נותנת 0.
התייחסות לאינדקס 0 כאל אי-התאמה. "aeiou".indexOf('a') הוא 0, כלומר יש התאמה. בדוק אם הערך הוא -1, או ב-PHP השווה את strpos ל-false באמצעות !==, כי שם 0 == false.
קריאה ל-strlen(s) בתנאי הלולאה ב-C. היא עוברת על כל המחרוזת בכל איטרציה, ולכן 5 × 10^4 תווים דורשים בערך 2.5 × 10^9 צעדים. עצור בתו הסיום '\0', או חשב את האורך פעם אחת לפני הלולאה.

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

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

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

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

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

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

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

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

עם חמש אותיות, שלושתן פועלות בזמן קבוע לכל תו, וההבדל במהירות ביניהן קטן מכדי להיות משמעותי. בחרו באפשרות שהכי קריאה בשפה שלכם: switch ב־C, ב־C++ או ב־Go, קבוצה או חיפוש במחרוזת ב־Python, ב־JavaScript או ב־Ruby.

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

קלט

s = "Interview"

צפוי