[Leetcode] 249. מיתרים קבוצתיים

249 Group Shifted Strings



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



הסיבה היא זו. קח את הקבוצה הראשונה, למשל, 'abc' => 'bcd' => 'xyz'
ביניהם, כלל אחד הוא ba = cb = dc = 1. או xa = yb = zc = 23. כלומר, bcd יכול להיות abc כל עוד הוא עובר שמאלה פעם אחת, ו- xyz יכול להיות גם abc כל עוד הוא משמרות עזבו 23 פעמים. אם ניקח את המחרוזת שהדמות הראשונה שלה היא כמקרה הבסיס של קבוצה זו. אנחנו רק צריכים לחשב את המרחק בין התו הראשון ל- a, ואתה יודע כמה פעמים המחרוזת כולה מועברת שמאלה כדי להפוך לקבוצת מקרי בסיס. ואז אנו משתמשים בטבלת hash כדי לשמור על חברי הצוות. (חברי הקבוצה עשויים שלא לכלול את המקרה הבסיסי)



לדוגמה, abc, efg, bdf, efi



1. ב- abc, המרחק בין a ל- a הוא 0, כך שהמחרוזת לא צריכה לנוע שמאלה, זהו מקרה בסיס. בטבלת החשיש יש קבוצה abc והחבר abc
2. ב- efg, המרחק בין e ל- a הוא 4, ולכן צריך להעביר את המחרוזת שמאלה על ידי 4 רווחים, ואז להפוך למקרה הבסיסי של abc, ואז לקבוצת abc של טבלת החשיש הוסף חבר efg
3. המרחק בין bdf, b ו- a הוא 1, ולכן המחרוזת כולה מועברת שמאלה ב- 1 כדי להפוך למקרה הבסיסי של אס, ויש טבלת חשיש אס נוסף של הקבוצה. חבר הוא bdf
4. המרחק בין efi, e ו- a הוא 4, כך שהמשמרת השמאלית הכוללת היא פי 4, והיא הופכת לאס, לכן הוסף חבר אחר בקבוצת האס בטבלת החשיש ל- efi בעוז.

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

public List groupStrings(String[] strings) { Map strMap = new HashMap() for (String str : strings) { String shiftedKey = _getShiftedString(str) if (!strMap.containsKey(shiftedKey)) strMap.put(shiftedKey, new LinkedList()) strMap.get(shiftedKey).add(str) } return new LinkedList(strMap.values()) } private String _getShiftedString(String a) { if (a.length() > 0) { char[] cArr = a.toCharArray() int diff = (int)cArr[0] - 'a' cArr[0] = 'a' for (int i = 1 i = diff) ? (int)cArr[i] - diff : (int)cArr[i] - diff + 26) } return new String(cArr) } else { return a } }