CTCI 1.9 स्ट्रिंग रोटेशन: एक isSubstring कॉल

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: एक isSubstring कॉल से जांचें कि s२, s१ का रोटेशन है या नहीं: s१ को खुद से जोड़ें और पूछें कि s२ अंदर है या नहीं। शुरुआती लोगों के लिए जावा वॉकथ्रू।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

अक्षरों की मणियों वाला एक गोल हार। आप दो मणियों के बीच खोलते हैं, लूप घुमाते हैं ताकि कोई नई मणि आगे आ जाए, फिर फिर से बंद कर देते हैं। मणियां वही हैं, चक्रीय क्रम वही है। सिर्फ शुरुआती बिंदु बदला। यही स्ट्रिंग रोटेशन है।

यह पोस्ट सीटीसीआई जावा सीरीज़ की समस्या १.९ है: दो स्ट्रिंग दी गई हैं, तय करें कि एक दूसरे का रोटेशन है या नहीं, और isSubstring को केवल एक बार कॉल कर सकते हैं।

---

समस्या सादे शब्दों में

आपको दो स्ट्रिंग मिलती हैं, s1 और s2।

• s1 का रोटेशन मतलब: कोई इंडेक्स i चुनो, सफिक्स s1[i..] लो, फिर प्रीफिक्स s1[0..i) पीछे चिपका दो। उदाहरण: waterbottle को wat के बाद घुमाओ तो erbottlewat बनता है।
• एक हेल्पर isSubstring(big, small) दिया है जो तब true देता है जब small कहीं big के अंदर दिखे।
• isRotation(s1, s2) लिखो जो तभी true दे जब s2 वास्तव में s1 का कोई रोटेशन हो।
• इंटरव्यू की खास शर्त: isSubstring को अधिकतम एक बार कॉल करो।

कैरेक्टर केस-सेंसिटिव मानो। "Abc" "bca" का रोटेशन नहीं है।

---

कोड से पहले कैसे सोचें

ब्रूट फोर्स (इसे अंतिम जवाब की तरह पेश न करें)

हर कट पॉइंट i (० से n-१) पर s1.substring(i) + s1.substring(0, i) बनाकर s2 से मिलाओ। O(n) उम्मीदवार, हर तुलना O(n), यानी O(n²) समय और ढेर सारी अस्थायी स्ट्रिंग। एक-कॉल वाला नियम भी नहीं लगता।

वह विचार जो एक-कॉल सीमा खोलता है

अगर s2, s1 का रोटेशन है, तो s1 को x + y और s2 को y + x लिखा जा सकता है (कुछ स्ट्रिंग x और y के लिए; खाली भी हो सकती हैं)।

s1 को खुद से जोड़ो:

s1 + s1 = x + y + x + y

बीच का टुकड़ा y + x है, यानी ठीक s2। इसलिए s1 का हर रोटेशन s1 + s1 की सबस्ट्रिंग है।

उल्टी दिशा के लिए एक और गार्ड चाहिए: लंबाई समान होनी चाहिए। वरना छोटी स्ट्रिंग डबल किए गए टेक्स्ट में बैठ सकती है बिना बराबर-लंबाई वाले रोटेशन के।

पूरी जांच:

१. समान लंबाई (और आमतौर पर नॉन-नल)। २. एक बार isSubstring(s1 + s1, s2)।

खाली स्ट्रिंग: दोनों खाली समान लंबाई वाली हैं, "" + "" अभी भी "" है, और isSubstring("", "") true होना चाहिए। एक खाली और एक गैर-खाली लंबाई पर फेल।

---

जावा समाधान

/**
 * true अगर s2, s1 का रोटेशन है; अधिकतम एक isSubstring कॉल।
 * उदाहरण: "waterbottle" और "erbottlewat" -> true.
 */
public static boolean isRotation(String s1, String s2) {
    if (s1 == null || s2 == null) {
        return false;
    }
    // रोटेशन लंबाई बचाता है। अलग लंबाई: असंभव।
    if (s1.length() != s2.length()) {
        return false;
    }
    // वैकल्पिक: दोनों खाली स्ट्रिंग समान रोटेशन।
    // s1 + s1 अभी भी खाली; isSubstring खाली-में-खाली के लिए true दे।
    String doubled = s1 + s1;
    return isSubstring(doubled, s2);
}

/**
 * true अगर small, big के अंदर है। इंटरव्यू में यह "दिया हुआ" माना जाता है।
 * असली जावा में indexOf से लागू कर सकते हो।
 */
public static boolean isSubstring(String big, String small) {
    if (big == null || small == null) {
        return false;
    }
    return big.indexOf(small) != -1;
}

क्लासिक उदाहरण का ट्रैक:

कदम	मान
s1	waterbottle
s2	erbottlewat
लंबाई	दोनों ११, ठीक
s1 + s1	waterbottlewaterbottle
isSubstring	wat के बाद erbottlewat मिलता है

एक कॉल। काम पूरा।

---

जटिलता

	लागत	क्यों
समय	आमतौर पर O(n)	s1+s1 बनाना O(n)। indexOf औसत में O(n) / भोले सबसे बुरे में O(n·m)। इंटरव्यू जवाब: अच्छी सबस्ट्रिंग खोज के साथ लंबाई में रैखिक काम।
अतिरिक्त स्थान	O(n)	डबल स्ट्रिंग की लंबाई २n।

सबसे बुरे मामले में दोनों स्ट्रिंग पढ़नी पड़ती हैं, इसलिए रैखिक क्रम सही परिमाण है।

---

वे किनारे के केस जो इंटरव्यूअर छूते हैं

१. नल इनपुट। false लौटाओ (या कॉन्ट्रैक्ट कहे तो थ्रो)। चुनाव जोर से बोलो। २. अलग लंबाई। तुरंत false। isSubstring कॉल की जरूरत नहीं (शून्य कॉल भी "अधिकतम एक" को पूरा करती है)। ३. एक जैसी स्ट्रिंग। शून्य रोटेशन। s1+s1 में s1 है। true। ४. खाली स्ट्रिंग। दोनों खाली: true। एक खाली: लंबाई से false। ५. एक कैरेक्टर। "a" और "a" true; "a" और "b" false। ६. दोहराए गए अक्षर। "aaaa" और "aaaa" true। "aaba" और "abaa" true (रोटेशन)। डबल-स्ट्रिंग टेस्ट ही करो; खास केस मत गढ़ो। ७. केस और स्पेस। जब तक समस्या केस नज़रअंदाज़ न कहे, "Ab" "bA" का रोटेशन नहीं। डिफ़ॉल्ट: सटीक मिलान। ८. isSubstring एक से ज़्यादा बार। यही सवाल का मूल है। सारे रोटेशन खुद बनाना सही हो तो भी भावना हारता है।

---

आम गलतियां

• लंबाई जांच भूलकर सिर्फ isSubstring(s1+s1, s2) चलाना। छोटी स्ट्रिंग डबल स्रोत में छिपकर पास हो सकती है।
• कट पॉइंट पर लूप में isSubstring कॉल करना। बजट खत्म।
• बिना भूमिका संभाले s2+s2 पर contains। डबल स्ट्रिंग मूल होनी चाहिए (लंबाई बराबर और वे एक-दूसरे के रोटेशन हों तो दोनों में से कोई भी चल सकता है)। एक कहानी रखो: s1 डबल करो, s2 खोजो।
• दोनों स्ट्रिंग सॉर्ट करना। वह एनाग्राम जांचता है, रोटेशन नहीं। "abcd" और "acbd" एनाग्राम हैं, रोटेशन नहीं।

---

दोस्त को समझाने वाला सार

रोटेशन वही चक्रीय हार है, बस अलग क्लैस्प से खोला गया।

अगर s2 सच में s1 का रोटेशन है, तो s2 कोई y + x है जबकि s1 x + y है। s1 दो बार लिखो तो वह y + x बीच में बैठता है। इसलिए समान लंबाई जांचो, फिर एक बार पूछो: क्या s2, s1 + s1 की सबस्ट्रिंग है?

पूरा ट्रिक यही है। एक अच्छी अंतर्दृष्टि लूपों के घोंसले से बेहतर है।

---

अभ्यास

१. बिना देखे isRotation याद से लिखो। २. कागज़ पर isRotation("waterbottle", "erbottlewat") ट्रेस करो। ३. गलत केस ट्रेस करो: isRotation("waterbottle", "bottlewaterx") (लंबाई) और isRotation("abc", "acb") (एनाग्राम, रोटेशन नहीं)। ४. समझाओ कि दोनों तरफ सॉर्ट करना गलत औजार क्यों है।

यह अध्याय १ (ऐरे and Strings) बंद करता है। आगे: लिंक्ड लिस्ट, Remove Dups। पूरी सीरीज़ का नक्शा: सीटीसीआई जावा।