Count a Character

Q: האם ספירת תווים רגישה לאותיות רישיות וקטנות?

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

Q: האם מותר לי להשתמש בפונקציית count מובנית בריאיון?

בדרך כלל כן, כל עוד אפשר לומר מה העלות. הפונקציה str.count של Python ופונקציות דומות עדיין קוראות את כל המחרוזת, ולכן סיבוכיות הזמן שלהן היא O(n) . מראיינים רבים יבקשו ממך לאחר מכן לכתוב בעצמך את הלולאה, אז כדאי להיות מוכן להציג אותה.

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

+10

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

פונקציה

countChar(s: string, c: string) → integer

sstring: מחרוזת האותיות באנגלית לחיפוש
cstring: האות האחת שיש לספור
מחזירהinteger: כמה תווים ב-s שווים ל-c

אילוצים

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

דוגמאות

קלט: s = "Mississippi"c = "s"
פלט: 4
הסבר: ב־Mississippi יש s במיקומים 2, 3, 5 ו־6, בספירה מ־0, ולכן התשובה היא 4.

קלט: s = "Banana"c = "b"
פלט: 0
הסבר: Banana מתחילה באות גדולה B, והחיפוש הוא אחר אות קטנה b. השתיים שונות, ולכן אין התאמות והתשובה היא 0.

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

שאלת המשך

מה אם c יכולה להיות מילה שמורכבת מכמה אותיות, כמו ss? האם התאמות חופפות נחשבות, ואיך הלולאה שלך משתנה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

מחקו כל c והשוו בין האורכים

האינטואיציה

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

עבור Mississippi ו-s, העותק הוא Miiippi. יש בו 7 תווים לעומת 11 במקור, כך ש-c הופיע 4 פעמים. עם Banana ו-b, שום דבר לא מוסר כי B גדולה אינה תואמת, וההפרש הוא 0.

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

אלגוריתם

יוצרים עותק של s שמשמיט כל תו ששווה ל־c.
מודדים את האורך של s ואת אורך העותק.
מחזירים את האורך של s פחות אורך העותק.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

מעבר אחד עם מונה

האינטואיציה

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

עבור Mississippi, המונה עולה באינדקסים 2, 3, 5 ו־6 ומסתיים ב־4. כל תו מושווה פעם אחת, ולא נשמר שום דבר נוסף.

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

אלגוריתם

קרא את האות המבוקשת מתוך c והגדר count = 0.
עבור על s תו אחד בכל פעם.
אם התו שווה לאות המבוקשת, הוסף 1 ל־count.
החזר את count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

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

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

התעלמות מרישיות. המרה של שני הצדדים לאותיות קטנות גורמת לכך ש־Banana עם b מחזיר 1, אבל המשימה מבקשת התאמות מדויקות, ולכן התשובה היא 0.
השוואת תו למחרוזת. ב־Java, C, C++, C# ו־Go, c מגיע כמחרוזת, ואילו s.charAt(i) או s[i] הוא תו יחיד. יש לקחת את c[0] (או את c.charAt(0)) פעם אחת לפני הלולאה.
השוואת מחרוזות באמצעות == ב־Java. String.valueOf(s.charAt(i)) == c משווה זהות של אובייקטים וכמעט תמיד מחזיר false. יש להשוות ערכי char, או להשתמש ב־equals.
קריאה ל־strlen(s) בתנאי הלולאה ב־C. הפונקציה עוברת על כל המחרוזת בכל צעד, ולכן 5 × 10^4 תווים עולים בערך 2.5 × 10^9 צעדים. יש לעצור בתו הסיום '\0' במקום זאת.

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

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

התחילו מונה ב־0 ועברו על המחרוזת פעם אחת. בכל פעם שהתו הנוכחי שווה לתו שאתם מחפשים, הוסיפו 1. כשהלולאה מסתיימת, המונה הוא התשובה, וזמן הריצה הוא O(n) עם זיכרון נוסף של O(1).

האם ספירת תווים רגישה לאותיות רישיות וקטנות?

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

האם מותר לי להשתמש בפונקציית count מובנית בריאיון?

בדרך כלל כן, כל עוד אפשר לומר מה העלות. הפונקציה str.count של Python ופונקציות דומות עדיין קוראות את כל המחרוזת, ולכן סיבוכיות הזמן שלהן היא O(n). מראיינים רבים יבקשו ממך לאחר מכן לכתוב בעצמך את הלולאה, אז כדאי להיות מוכן להציג אותה.

איך תספור את כל התווים בבת אחת?

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

Python

def countChar(s, c):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

קלט

s = "Mississippi"
c = "s"

צפוי