לא מסכים איתך..

ראיתי את הפיתרון שלך והוא לא פתרון רקורסיבי קלאסי.

ברקורסיה אתה אמור כמו שאמרתי לחלק את הבעייה לבעייה פשוטה ואת ההמשך לפתור בצורה רקורסיבית וזה לא מה שאתה עושה...

דווקא הפתרון שלי הוא רקורסיה קלאסית.

פותרים עבור תת מחרוזת וממשיכים בקריאה רקורסיבית

מה זה לעזאזל רקורסיה קלאסית?

tomryh

אני ממש לא מסכים עם מה שאתה אומר.

הרקורסיה שאנחנו מציעים היא "קלאסית" במובן הזה -

א) נבדק תנאי יציאה

ב) בונים תת מחרוזות

ג) נקריאת הרקורסיה על תת המחרוזות

ואין שום שימוש בלולאות או משתני בקרה כלשהם

זה לא רקורסיה "קלאסית"?

הנה הסבר לוגי של הפתרון:

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

אלו הם למעשה שני איברים "נוכחיים" והם תמיד צריכים להיות שווים.

החוכמה היא מתי לקדם את האיבר הנוכחי -

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

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

במחרוזת השניה האיבר מקודם תמיד.

למעשה אנחנו נגרום לכל הכפולים ברשימה השניה להיות מושווים מול האיבר האחרון בתת מחרוזת ברשימה הראשונה

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

במחרוזת הראשונה יש שתי תתי מחרוזות "aaa" ן "bbb" ורואים שאנחנו לא מקדמים את האיבר הבא של הרשימה הראשונה עד הגענו לתחילת התת מחרוזת השניה במחרוזת השניה - לפי ההשוואה בין האיברים הבאים בשתי הרשימות

האלגוריתם המלא הוא כזה -

הפונקציה

public static boolean isTrans (CharList list1, CharList list2)

מקבלת שתי רשימות.

1) בדיקת תנאי עצירה

1.1) אם שתי הרשימות ריקות (_head == NULL) - בדקנו את כל התווים בשתי המחרוזות ולא מצאנו אי התאמה - החזר "אמת"

1.2) אם אחת מהמחרוזות ריקה והשניה לא - ז"א ולאחת מהן יש תווים מיותרים - החזר "שקר"

1.3) אם שתיהן לא ריקות, השווה את האיברים הראשונים, אם הם לא זהים - החזר "שקר"

2) קביעת האיברים הבאים

2.1) קדם את האיבר הבא ברשימה שניה ללא תנאי

CharNode nextNode2 = list2._head.getNext()

2.2) אם יש איבר הבא ברשימה אחת (אינו ריק)

2.2.1) אם האיבר הנוכחי זהה לאיבר הבא - קדם אותו

if (list1._head.getValue() == list1._head.getNext().getValue())
 CharNode nextNode1 = list1._head.getNext()

2.2.2) אם האיבר הנוכחי לא זהה לאיבר הבא - בדוק את האיבר הבא ברשימה ראשונה מול האיבר הבא ברשימה שניה, קדם אותו אם הם זהים

if (nextNode2 != NULL && nextNode2.getValue() == list1._head.getNext().getValue())
 CharNode nextNode1 = list1._head.getNext()

2.2) אם אין איבר הבא ברשימה אחת (הוא ריק)

2.2.1) בדוק אם האיבר הבא ברשימה שניה ריק. אם כן, קדם את האיבר הבא ברשימה ראשונה - בדיקה זו נועדה למען תוים כפולים בתת מחרוזת האחרונה

3) קריאה לרקורסיה

בנה רשימות חדשות שראשיהן הן האיברים הבאים שנקבעו מקודם וקרא למתודה שוב

return isTrans(new CharList(nextNode1), new CharList(nextNode2));

זהו

אם זה לא ברור, אני אפרסם את הפתרון המלא