सीटीसीआई १.५ वन अवे: एक संपादन, जावा में एक पास

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: जाँचें कि दो स्ट्रिंग अधिकतम एक इंसर्ट, रिमूव या रिप्लेस से अलग हैं या नहीं। लंबाई का नियम, दो पॉइंटर वाला एक स्कैन, और ज़ोर से समझाने लायक साफ़ जावा।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

आप पासवर्ड एक बार टाइप करते हैं, एक अक्षर गलत हो जाता है, और सिस्टम फिर भी खुल जाता है। यह जादू नहीं है। किसी ने तय किया कि एक छोटा संपादन काफी नज़दीक है, और दो नहीं।

पूरी समस्या यही है: दो स्ट्रिंग दी हों, तय करें कि पहली को दूसरी में बदला जा सकता है अधिकतम एक इन संक्रियाओं से:

१. एक अक्षर रिप्लेस (pale → bale)
२. एक अक्षर इंसर्ट (ple → pale)
३. एक अक्षर रिमूव (pale → ple)

शून्य संपादन (स्ट्रिंग बराबर हों) भी सत्य माना जाता है। दो या अधिक संपादन असत्य।

यह सीटीसीआई शैली की समस्या १.५, वन अवे, अध्याय १ (ऐरे और स्ट्रिंग) है। हम इसे छोटी स्ट्रिंग पर एक पास में, सादे जावा में हल करेंगे।

श्रृंखला का घर: जावा में सीटीसीआई। पिछला: १.४ पैलिंड्रोम परम्यूटेशन। अगला: १.६ स्ट्रिंग कम्प्रेशन।

---

रोज़मर्रा की तस्वीर

कागज़ पर दो लगभग एक जैसी खरीदारी सूचियाँ सोचें।

• एक चीज़ काट दी: रिमूव।
• एक अतिरिक्त चीज़ लिख दी: इंसर्ट।
• एक गलत वर्तनी सुधारी: रिप्लेस।

अगर सूचियाँ पहले से मेल खाती हैं, शून्य संपादन लगे। अगर दो जगह बदलीं, आप "एक दूर" नहीं हैं। किसी भारी डेटा संरचना की ज़रूरत नहीं। दोनों पर एक-एक उंगली रखकर चलें, और एक बेमेल को एक संपादन से समझाएँ।

---

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

इनपुट: दो स्ट्रिंग, a और b (इंटरव्यू उदाहरणों के लिए ऐस्की काफी है)।

आउटपुट: true अगर a को b में ० या १ संपादन (इंसर्ट, रिमूव, रिप्लेस) से बदला जा सके। वरना false।

उदाहरण:

पहली	दूसरी	परिणाम	क्यों
pale	ple	सत्य	a हटाएँ
pales	pale	सत्य	s हटाएँ (या छोटी में जोड़ें)
pale	bale	सत्य	p को b से बदलें
pale	bake	असत्य	दो रिप्लेस
pale	pale	सत्य	शून्य संपादन
a	``	सत्य	एक रिमूव
abc	abxcd	असत्य	लंबाई का अंतर २

ज़ोर से पूछने लायक सवाल:

• खाली स्ट्रिंग चलें? हाँ, सामान्य मानें।
• केस संवेदनशील? हाँ, जब तक पूछने वाला न कहे। 'A' और 'a' अलग।
• शून्य संपादन सत्य? हाँ। "वन अवे" अक्सर मतलब अधिकतम एक।

---

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

कदम १: लंबाई ज़्यादातर केस काट देती है

अगर लंबाइयों में अंतर १ से अधिक हो, कम से कम दो इंसर्ट (या रिमूव) चाहिए। तुरंत असत्य लौटाएँ।

|len(a) - len(b)| > 1  →  false

यह मुफ़्त है, और इंटरव्यूअर पहले यही सुनना पसंद करते हैं।

कदम २: समान लंबाई मतलब सिर्फ रिप्लेस

लंबाइयाँ बराबर हों तो एक संपादन में इंसर्ट/रिमूव मदद नहीं करते (वे लंबाई बदलते हैं)। दोनों स्ट्रिंग साथ चलाएँ। बेमेल गिनें। दूसरा बेमेल आए तो असत्य। अंत में शून्य या एक बेमेल ठीक।

कदम ३: लंबाई अंतर १ मतलब इंसर्ट या रिमूव

सामान्यता खोए बिना छोटी को s और लंबी को t कहें। s में एक इंसर्ट वही है जो t से एक रिमूव।

दो इंडेक्स i (s में) और j (t में) से चलें:

• अगर s[i] == t[j], दोनों आगे।
• अगर अलग, वही आपका एकमात्र संपादन होना चाहिए। सिर्फ j आगे (लंबी में अतिरिक्त अक्षर छोड़ें)। अगर संपादन पहले खर्च हो चुका, असत्य।

लूप खत्म होने पर या शून्य संपादन से मेल हुआ, या ठीक एक अतिरिक्त अक्षर छोड़ा। दोनों में सत्य (लंबी की बची पूँछ अधिकतम एक अक्षर, और लंबाई जाँच यही गारंटी देती है)।

कदम ४: एक मेथड, एक पास

इंटरव्यू कोड में तीन अलग फ़ंक्शन ज़रूरी नहीं। अक्षर न मिलें तभी शाखा लें, तो एक स्कैन रिप्लेस और इंसर्ट/रिमूव दोनों संभाल लेता है।

---

जावा: एक-पास समाधान

public final class OneAway {

    /**
     * Returns true if first and second are at most one edit apart
     * (insert, remove, or replace a single character).
     */
    public static boolean oneEditAway(String first, String second) {
        if (first == null || second == null) {
            return first == second;
        }

        int len1 = first.length();
        int len2 = second.length();
        if (Math.abs(len1 - len2) > 1) {
            return false;
        }

        // s = shorter (or equal), t = longer (or equal)
        String s = len1 <= len2 ? first : second;
        String t = len1 <= len2 ? second : first;

        int i = 0; // index in s
        int j = 0; // index in t
        boolean foundEdit = false;

        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
                continue;
            }

            // Characters differ: this must be our only edit
            if (foundEdit) {
                return false;
            }
            foundEdit = true;

            if (s.length() == t.length()) {
                // Same length: treat as replace, move both
                i++;
                j++;
            } else {
                // Different length: skip the extra char in the longer string
                j++;
            }
        }

        // If longer has one leftover char and we never edited, that leftover is the insert.
        // Length check already limits leftovers to at most one.
        return true;
    }
}

ट्रेस: pale बनाम ple (रिमूव / इंसर्ट)

• s = "ple", t = "pale"
• p == p → दोनों आगे
• l != a → पहला संपादन, t में a छोड़ें (सिर्फ j++)
• l == l, e == e → पूरा, सत्य

ट्रेस: pale बनाम bale (रिप्लेस)

• लंबाइयाँ बराबर
• p != b → पहला संपादन, दोनों आगे
• बाकी मेल → सत्य

ट्रेस: pale बनाम bake (दो रिप्लेस)

• p != b → पहला संपादन
• a == a
• l != k → दूसरा संपादन → असत्य

---

समय और स्थान

समय	ओ(एन) जहाँ एन छोटी स्ट्रिंग की लंबाई (एक पास, प्रति अक्षर स्थिर काम)
स्थान	अतिरिक्त ओ(१) (कुछ इंडेक्स और एक फ़्लैग; नई स्ट्रिंग नहीं)

अक्षर गिनती वाला मैप नहीं चाहिए। यहाँ क्रम मायने रखता है (abc बनाम cba एक दूर नहीं), इसलिए फ़्रीक्वेंसी टेबल झूठ बोलेगी।

---

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

१. बराबर स्ट्रिंग: oneEditAway("same", "same") → सत्य।
२. खाली और एक अक्षर: ("", "x") → सत्य; ("", "xy") → असत्य।
३. शुरुआत में संपादन: ("abc", "xabc") → सत्य (आगे इंसर्ट)।
४. अंत में संपादन: ("abc", "abcd") → सत्य।
५. बीच में संपादन: ("abc", "axc") → सत्य।
६. नल नीति: तय करें और बोलें। ऊपर का कोड दो नल को बराबर, मिश्रित नल को असत्य मानता है। कुछ टीमें नल पूरी तरह मना करती हैं।
७. यूनिकोड / सरोगेट: इंटरव्यू में अक्सर बीएमपी अक्षर। charAt ठीक। असल दुनिया के ग्रेफीम अलग उत्पाद समस्या हैं।

छोटा स्व-जाँच हार्नेस:

public static void main(String[] args) {
    assert oneEditAway("pale", "ple");
    assert oneEditAway("pales", "pale");
    assert oneEditAway("pale", "bale");
    assert !oneEditAway("pale", "bake");
    assert oneEditAway("pale", "pale");
    assert oneEditAway("", "a");
    assert !oneEditAway("abc", "abxcd");
    System.out.println("ok");
}

---

आम गलतियाँ

• लंबाई का शॉर्टकट भूलना। उसके बिना भी सही हो सकते हैं, पर काम बर्बाद और आसान अर्ली एग्ज़िट छूट जाती है।
• इंसर्ट पर गलत पॉइंटर चलाना। अलग लंबाई पर बेमेल के बाद सिर्फ लंबी स्ट्रिंग आगे बढ़े।
• दो रिप्लेस अनुमति देना। foundEdit फ़्लैग ही मूल बात है। रीसेट न करें; दूसरा बेमेल = असफल।
• एनाग्राम दूरी को संपादन दूरी समझना। वन अवे नहीं है "वही अक्षरों का मल्टीसेट।" क्रम तय रहता है, सिवाय एक संपादन के।
• पूरा लेवेंशटाइन डीपी बनाना। क्लासिक संपादन दूरी ओ(एन·एम) है। अधिकतम एक संपादन के लिए ज़्यादा है। रैखिक स्कैन अपेक्षित है।

---

दोस्त को समझाएँ

दो स्ट्रिंग एक दूर हैं अगर अंतर एक रिप्लेस, इंसर्ट या डिलीट से ठीक हो जाए (या पहले से मेल खाएँ)।

पहले लंबाइयाँ देखें। अंतर एक से बड़ा? खत्म, असत्य।

फिर दोनों चलाएँ। अक्षर मिलें तो चलते रहें। पहली बार न मिलें तो अपनी एक अनुमति खर्च करें: लंबाइयाँ बराबर हों तो रिप्लेस मानकर दोनों उंगलियाँ आगे; अलग हों तो लंबे पक्ष का अतिरिक्त अक्षर छोड़ें। दूसरा मतभेद असत्य।

यह एक पास है, अतिरिक्त मेमोरी स्थिर, और व्हाइटबोर्ड पर आसानी से बोला जाता है।

---

अभ्यास संकेत

कोड ढकें। सिर्फ लंबाई नियम और दो पॉइंटर नियमों से oneEditAway लिखें। फिर उदाहरण तालिका ज़ोर से चलाएँ। जब स्वचालित लगे, १.६ स्ट्रिंग कम्प्रेशन खोलें।