Remove Vowels

Q: איך מסירים תנועות ממחרוזת?

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

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

מעבר אחד הוא בזמן O(n) , כי כל תו עובר בדיקת תנועה אחת בזמן קבוע. הפלט דורש O(n) מקום במקרה הגרוע ביותר, כאשר אין ב- s תנועות כלל. קריאה ל-replace פעם אחת עבור כל תנועה היא גם O(n) , אבל היא קוראת את המחרוזת עשר פעמים.

Q: אפשר להסיר תנועות באמצעות ביטוי רגולרי?

כן. החלפת התבנית [aeiouAEIOU] במחרוזת ריקה עושה זאת בקריאה אחת ברוב השפות. היא רצה ב־ O(n) , כמו הלולאה, אבל מראיינים בדרך כלל מבקשים ממך לכתוב את הלולאה כדי שיוכלו לראות את בדיקת התנועות ואת אופן בניית התוצאה.

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

+10

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

פונקציה

removeVowels(s: string) → string

sstring: מחרוזת האותיות באנגלית שיש לנקות
מחזירהstring: s עם כל התנועות שהוסרו ושאר האותיות בסדרן המקורי

אילוצים

1 ≤ s.length ≤ 3 × 10⁴
s מכילה רק אותיות באנגלית (a עד z, A עד Z).
s מכילה לפחות אות אחת שאינה תנועה, ולכן התשובה לעולם אינה ריקה.

דוגמאות

קלט: s = "Interview"
פלט: "ntrvw"
הסבר: מחיקת I, e, i ו-e מתוך Interview משאירה את n, t, r, v, w בסדר הזה. גם I הגדולה היא תנועה, ולכן היא נמחקת.

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

קלט: s = "EuropeanUnion"
פלט: "rpnnn"
הסבר: שמונה מתוך שלוש עשרה האותיות של EuropeanUnion הן תנועות, כולל האותיות הגדולות E ו־U. חמש העיצורים שנותרו, r, p, n, n, n, שומרים על הסדר שלהם ונקראים rpnnn.

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

שאלת המשך

מה אם הטקסט יכול להכיל כל אות Unicode, כמו É או ö? אילו מהן הן תנועות, וכיצד משתנה הבדיקה שלך?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

מחקו כל תנועה במעבר נפרד

האינטואיציה

רוב השפות יכולות למחוק כל עותק של תו אחד ממחרוזת בקריאה אחת: מחליפים אותו בכלום. עושים זאת עשר פעמים, פעם אחת עבור כל אחד מהתווים a e i o u A E I O U, וכך לא נשארת אף תנועה. העיצורים לעולם אינם נוגעים בהם, ולכן הם שומרים על הסדר ועל האותיות הגדולות והקטנות שלהם.

עבור Interview, המעבר עבור e נותן Intrviw, המעבר עבור i נותן Intrvw, והמעבר עבור I נותן ntrvw. שבעת המעברים האחרים אינם מוצאים דבר להסיר.

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

אלגוריתם

קח את עשר אותיות התנועה aeiouAEIOU אחת בכל פעם.
עבור כל אחת מהן, החלף כל מופע שלה בתוך s בכלום.
לאחר עשרת המעברים, החזר את מה שנותר מ־s.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

מעבר אחד ששומר על העיצורים

האינטואיציה

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

עבור EuropeanUnion, המעבר מדלג על E, u, o, e, a, U, i ו-o, ומוסיף את r, p, n, n, n: התוצאה היא rpnnn.

כל תו דורש בדיקה אחת בזמן קבוע (חיפוש בקבוצה, switch או חיפוש במחרוזת בת עשר אותיות), ולכן זמן הריצה הוא O(n). אספו את האותיות בבונה מחרוזות או ברשימה והמירו אותן למחרוזת פעם אחת בסוף; הגדלת מחרוזת בלתי ניתנת לשינוי באמצעות += תעתיק אותה בכל שלב. הפלט עצמו דורש O(n) מקום.

אלגוריתם

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

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

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

רוב התשובות השגויות נובעות מבדיקת התנועות או מהאופן שבו מחרוזת התוצאה גדלה.

שוכחים תנועות באותיות גדולות. בדיקה של aeiou בלבד הופכת את Interview ל-Intrvw במקום ל-ntrvw. בדקו את כל עשר האותיות, או הפכו את האותיות לקטנות לפני הבדיקה, והשאירו את האות המקורית בפלט.
משנים את האותיות שנשמרות לאותיות קטנות. אם הופכים את כל המחרוזת לאותיות קטנות כדי לקצר את הבדיקה, QUEUEING הופכת ל-qng במקום ל-QNG. הפכו לאותיות קטנות רק את העותק שאתם בודקים, והוסיפו את האות המקורית.
מוחקים תוך כדי מעבר קדימה לפי אינדקס. הסרת s[i] מזיזה את האות הבאה למיקום i, ואז i++ מדלג עליה, כך ש-aab הופכת ל-ab. בנו מחרוזת חדשה, או עברו בעזרת מיקומי קריאה וכתיבה נפרדים.
מגדילים מחרוזת בלתי ניתנת לשינוי באמצעות += בתוך לולאה. ב-Java או ב-C# כל שלב מעתיק את המחרוזת כולה — בערך 4.5 × 10^8 העתקות תווים עבור 3 × 10^4 אותיות. השתמשו בבונה מחרוזות או ברשימה, וחברו אותה פעם אחת.

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

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

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

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

מעבר אחד הוא בזמן O(n), כי כל תו עובר בדיקת תנועה אחת בזמן קבוע. הפלט דורש O(n) מקום במקרה הגרוע ביותר, כאשר אין ב-s תנועות כלל. קריאה ל-replace פעם אחת עבור כל תנועה היא גם O(n), אבל היא קוראת את המחרוזת עשר פעמים.

אפשר להסיר תנועות באמצעות ביטוי רגולרי?

כן. החלפת התבנית [aeiouAEIOU] במחרוזת ריקה עושה זאת בקריאה אחת ברוב השפות. היא רצה ב־O(n), כמו הלולאה, אבל מראיינים בדרך כלל מבקשים ממך לכתוב את הלולאה כדי שיוכלו לראות את בדיקת התנועות ואת אופן בניית התוצאה.

למה לא למחוק את התנועות מהמחרוזת במקום?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "Interview"

צפוי

"ntrvw"