המחרוזת הכי קטנה שמכילה שתי מחרוזות

נגדיר: מחרוזת תווים s מכילה מחרוזת t אם כל התווים של t נמצאים במחרוזת s באותו סדר בו הם נמצאים ב-t (אבל יכולים להיות תווים נוספים ביניהם).
בהינתן מחרוזת str1 ומחרוזת str2 יש להחזיר את המחרוזת הקטנה ביותר המכילה את שתי המחרוזות.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:

אסור להשתמש במשתנים סטטיים (גלובליים)!
קיימות מספר תשובות חוקיות.

דוגמה 1:

קלט:

str1 = "A",
str2 = "B"

פלט:

AB

הסבר: המחרוזת הכי קטנה שמכילה את שתי המחרוזות היא "AB" או "BA".

דוגמה 2:

קלט:

str1 = "AA",
str2 = "A"

פלט:

AA

הסבר: המחרוזת הכי קטנה שמכילה את שתי המחרוזות היא "AA".

דוגמה 3:

קלט:

str1 = "AGGTAB",
str2 = "GXTXAYB"

פלט:

AGXGTXAYB

הסבר: המחרוזת הכי קטנה שמכילה את שתי המחרוזות היא "AGXGTXAYB".

דוגמה 4:

קלט:

str1 = "1A2B3C4D5E",
str2 = "A1B2C3D4E5"

פלט:

A1BA2CB3DC4ED5E

הסבר: המחרוזת הכי קטנה שמכילה את שתי המחרוזות היא "A1BA2CB3DC4ED5E".

דוגמה 5:

קלט:

str1 = "ABC",
str2 = "ACB"

פלט:

ACBC

הסבר: המחרוזת הכי קטנה שמכילה את שתי המחרוזות היא "ACBC".

דוגמה 6:

קלט:

str1 = "XYZ",
str2 = ""

פלט:

XYZ

הסבר: מחרוזת ריקה מוכלת בכל מחרוזת, לכן str1 עצמה היא המחרוזת הקטנה ביותר.

דוגמה 7:

קלט:

str1 = "HELLO",
str2 = "WORLD"

פלט:

WORHELDLO

הסבר: המחרוזת הכי קטנה שמכילה את שתי המחרוזות היא "WORHELDLO".

דוגמה 8:

קלט:

str1 = "ABC",
str2 = "XYZ"

פלט:

ABCXYZ

הסבר: המחרוזת הכי קטנה שמכילה את שתי המחרוזות היא "ABCXYZ", שמהווה שילוב של שתי המחרוזות המקוריות.

נשמרLn 1, Col 1

קלט:

str1 = "A",
str2 = "B"

הפלט המבוקש:

AB