To Lower Case

Q: איך ממירים מחרוזת לאותיות קטנות בלי להשתמש בפונקציה מובנית?

עבור בלולאה על התווים ובדוק את קוד התו של כל אחד מהם. אם הקוד נמצא בין 65 ( A ) ל־90 ( Z ), הוסף 32 כדי לקבל את האות הקטנה; השאר כל תו אחר ללא שינוי. חבר את התווים בחזרה למחרוזת.

Q: למה ההפרש בין אותיות גדולות לאותיות קטנות הוא 32?

ASCII ממקם את האותיות הגדולות בקודים 65 עד 90 ואת האותיות הקטנות בקודים 97 עד 122, וביניהן שישה סמלים. שני האלפביתים מסודרים באותו סדר, ולכן ההפרש בין כל זוג הוא 97 - 65 = 32 . 32 הוא ביט יחיד, ולכן הגדרת הביט הזה הופכת אות גדולה לאות הקטנה שלה.

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

כן. עבור אות גדולה, code | 32 מציב את הביט שמפריד בין שני המקרים ומפיק את האות הקטנה, ו־ code & ~32 מאפס אותו שוב. עדיין צריך לבדוק קודם את הטווח, כי אותו טריק עם ביטים ישנה גם ספרות וסמלים.

Q: מהי סיבוכיות הזמן של המרת מחרוזת לאותיות קטנות?

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

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

+10

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

פונקציה

toLowerCase(s: string) → string

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

אילוצים

1 ≤ s.length ≤ 10⁴
כל תו ב־s הוא אות באנגלית, ספרה או אחד מהסמלים !#$%&()*+-./:;<=>?@[]^_`{|}~.

דוגמאות

קלט: s = "Hello-World!"
פלט: "hello-world!"
הסבר: האותיות הגדולות H ו־W הופכות לאותיות הקטנות h ו־w. - ו־! אינם אותיות, ולכן הם נשארים במקומם.

קלט: s = "coddy_2026"
פלט: "coddy_2026"
הסבר: אין אות גדולה שאפשר לשנות. האותיות הקטנות, התו _ והספרות נשארים ללא שינוי.

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

שאלת המשך

האם תוכל לכתוב toUpperCase עם אותה לולאה, ולהסביר מדוע רק ביט אחד בקוד התו שונה בין A ל־a?

רמזים

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

נפתחו 0 מתוך 3

פתרון

כל שפה מגיעה עם פונקציה להמרה לאותיות קטנות, ובקוד שמיועד לסביבת ייצור כדאי להשתמש בה. מראיינים שואלים את השאלה הזאת כדי לבדוק אם ידוע לך מה הפונקציה עושה: תו הוא מספר, וב־ASCII כל אות גדולה נמצאת בדיוק 32 קודים לפני האות הקטנה שלה. בדוק אם קוד נמצא בין 'A' ל־'Z', והוסף לו 32 אם כן.

קריאה לפונקציה המובנית להמרת אותיות לאותיות קטנות

האינטואיציה

הפונקציות lower() של Python, toLowerCase() של JavaScript, downcase של Ruby והמקבילות שלהן בשפות אחרות כבר מבצעות את העבודה הזאת. ב-C וב-C++ יש את tolower עבור תו אחד, ולכן קוראים לה בתוך לולאה. כל תו נבדק פעם אחת, ולכן העבודה היא O(n), והמחרוזת החדשה תופסת מקום בנפח O(n).

חלק מהפונקציות האלה פועלות לפי הגדרות השפה של המחשב. בטורקית, האות הקטנה של I היא ı ללא נקודה, ולא i. לכן בגרסאות של Java ו-C# מבקשים כלל קבוע באמצעות Locale.ROOT ו-ToLowerInvariant, כדי שהתוצאה לא תשתנה ממחשב למחשב.

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

אלגוריתם

הפעילו את פונקציית המרת האותיות הקטנות של שפת התכנות שלכם על s, או הפעילו את tolower על כל תו ב-C וב-C++.
בקשו כלל קבוע שאינו תלוי בשפה, אם הפונקציה מציעה כלל כזה.
החזירו את התוצאה.

def toLowerCase(s):
    return s.lower()

הזז את קודי התווים של אותיות גדולות

האינטואיציה

כל תו נשמר כמספר. ב-ASCII, הקודים של A עד Z הם 65 עד 90, ושל a עד z הם 97 עד 122. שתי הסדרות מסודרות לפי האלפבית ומתחילות בהפרש של 32, לכן הקוד של האות הקטנה של כל אות גדולה הוא הקוד שלה ועוד 32: H היא 72 ו-h היא 104.

לכן עוברים על המחרוזת פעם אחת. אם קוד של תו נמצא בין 65 ל-90, מוסיפים 32; אחרת מעתיקים את התו כפי שהוא. בדיקת הטווח חשובה: הסימנים [, ^ ו-_ נמצאים בין Z ל-a, ו-@ נמצא ממש לפני A. בדיקה של code < 97 בלבד תהפוך את _ לסימן אחר.

כל תו נבדק פעם אחת, כלומר זמן הריצה הוא O(n). התוצאה היא מחרוזת חדשה באותו האורך, ונדרשים O(n) מקומות בזיכרון. כתיבה של 'a' - 'A' במקום 32 מבטאת את אותו הדבר ומסבירה מהיכן המספר מגיע.

אלגוריתם

העתיקו את s למערך של תווים או קודים.
עבור כל מיקום, קראו את קוד התו.
אם הקוד נמצא בין 'A' (65) ל־'Z' (90), הוסיפו 32.
הפכו את המערך בחזרה למחרוזת והחזירו אותה.

def toLowerCase(s):
    # Every capital letter sits 32 codes below its small letter: 'A' is 65, 'a' is 97.
    shift = ord("a") - ord("A")
    chars = []
    for ch in s:
        if "A" <= ch <= "Z":
            ch = chr(ord(ch) + shift)
        chars.append(ch)
    return "".join(chars)

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

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

הוספת 32 לכל תו שאינו אות קטנה. גם ספרות וסמלים ישתנו: 1 יהפוך ל־Q.
בדיקה של קצה אחד בלבד של הטווח. code < 'a' תופס גם את [, את _ ואת @, ו־code >= 'A' תופס גם כל אות קטנה.
שימוש ב־< במקום ב־<= בקצוות, כך ש־A או Z נשארות אותיות גדולות.
בניית התשובה באמצעות result = result + ch במחרוזת בלתי ניתנת לשינוי. בכל שלב מועתק כל מה שנצבר עד כה, ולכן הסיבוכיות ריבועית עבור n = 10^4.
ב־C, כתיבה לתוך הקלט או שכחה של '\0' המסיים. הקצה n + 1 בתים עבור העותק.

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

איך ממירים מחרוזת לאותיות קטנות בלי להשתמש בפונקציה מובנית?

עבור בלולאה על התווים ובדוק את קוד התו של כל אחד מהם. אם הקוד נמצא בין 65 (A) ל־90 (Z), הוסף 32 כדי לקבל את האות הקטנה; השאר כל תו אחר ללא שינוי. חבר את התווים בחזרה למחרוזת.

למה ההפרש בין אותיות גדולות לאותיות קטנות הוא 32?

ASCII ממקם את האותיות הגדולות בקודים 65 עד 90 ואת האותיות הקטנות בקודים 97 עד 122, וביניהן שישה סמלים. שני האלפביתים מסודרים באותו סדר, ולכן ההפרש בין כל זוג הוא 97 - 65 = 32. 32 הוא ביט יחיד, ולכן הגדרת הביט הזה הופכת אות גדולה לאות הקטנה שלה.

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

כן. עבור אות גדולה, code | 32 מציב את הביט שמפריד בין שני המקרים ומפיק את האות הקטנה, ו־code & ~32 מאפס אותו שוב. עדיין צריך לבדוק קודם את הטווח, כי אותו טריק עם ביטים ישנה גם ספרות וסמלים.

מהי סיבוכיות הזמן של המרת מחרוזת לאותיות קטנות?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "Hello-World!"

צפוי

"hello-world!"