कोष्ठक: बाएँ/दाएँ गिनती से सभी वैध कोष्ठक शृंखलाएँ (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.९: न जोड़े कोष्ठकों की हर वैध शृंखला बनाओ। बची खुली और बंद गिनती से बैकट्रैक, अवैध उपसर्ग जल्दी काटो, कैटलान गिनती समझो।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम्हें न खुले कोष्ठक और न बंद कोष्ठक से बनी हर वैध शृंखला चाहिए: किसी भी उपसर्ग में बंद की संख्या खुले से ज़्यादा न हो, और अंत में दोनों बराबर हों। न = ३ पर पाँच शृंखलाएँ मिलती हैं, तीन ( और तीन ) रखने के बीस तरीकों में से नहीं। ज़्यादातर बेतरतीब जगहें बीच में टूट जाती हैं।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाले क्लासिक "कोष्ठक बनाओ" सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८, रिकर्शन और डायनामिक प्रोग्रामिंग, समस्या ८.९।

१. रोज़मर्रा की उपमा

एक कोट-चेक काउंटर सोचो जहाँ न टिकट और न कोट हों।

टिकट देना ( है।
कोट वापस करना ) है।
जब कोई इंतज़ार न कर रहा हो तो कोट वापस नहीं कर सकते (वह बिना जोड़े ( का ) होगा)।
अंत में हर टिकट खर्च हो और हर कोट वापस मिले।

वैध क्रम वही हैं जहाँ "इंतज़ार कर रहे लोगों" की गिनती कभी ऋणात्मक न हो। अवैध क्रम पहले कोट लौटाने की कोशिश करते हैं, या अंत में टिकट बाहर छोड़ देते हैं।

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

२. सादा समस्या कथन

इनपुट: ऋणेतर पूर्णांक न, जोड़ों की संख्या।

आउटपुट: लंबाई २न की सभी शृंखलाएँ जो ठीक न अक्षर ( और न अक्षर ) इस्तेमाल करें और सही जोड़ी में हों।

उदाहरण:

न	वैध शृंखलाएँ
०	`[""]` (एक खाली शृंखला; एक रिवाज चुनो)
१	`["()"]`
२	`["(())", "()()"]`
३	`["((()))", "(()())", "(())()", "()(())", "()()()"]`

कोड से पहले साफ करो:

न = ०: खाली सूची या एक खाली शृंखला? यहाँ: एक खाली परिणाम (रिकर्शन का बेस केस)।
परिणामों का क्रम? ज़रूरी नहीं। जब तक शब्दकोश क्रम न माँगें, कोई भी क्रम ठीक।
सिर्फ ( और )? क्लासिक समस्या में हाँ। दूसरे प्रकार के कोष्ठक अलग सवाल हैं।
जावा में List<String> लौटाओ। सिर्फ प्रिंट मत करो; टेस्ट आसान हों इसलिए इकट्ठा करो।

तुमसे एक शृंखला जाँचना नहीं कहा गया (वह स्टैक वाली समस्या है)। तुम हर वैध शृंखला बनाते हो।

३. पहले सोचो

वैध की दो शर्तें

कोष्ठकों की शृंखला वैध तभी है जब:

१. हर उपसर्ग में #( ≥ #)। २. पूरी शृंखला पर #( = #) = न।

नियम १ )( और ())( काटता है। नियम २ बचे खुले काटता है।

सभी क्रमों का ब्रूट फोर्स कमज़ोर क्यों

ठीक न खुले और न बंद वाली सी(२न, न) शृंखलाएँ होती हैं। बहुत सी नियम १ पर गिरती हैं। न = ३ पर सी(६, ३) = २० उम्मीदवार और सिर्फ ५ वैध। बड़े न पर फासला और बढ़ता है। इंटरव्यू में बनाते समय काटना चाहते हैं, पहले सब बनाकर बाद में छानना नहीं।

बची बाईं और दाईं गिनती

रखो:

left: अभी और कितने ( रख सकते हो (शुरुआत न)।
right: अभी और कितने ) रख सकते हो (शुरुआत न)।

हर कदम पर:

१. अगर left > 0, तो ( रख सकते हो, फिर left - 1 से रिकर्स। २. अगर right > left, तो ) रख सकते हो (बंद का बजट खुले की बची गिनती से ज़्यादा है, मतलब रास्ते पर पहले से खुले बंद से ज़्यादा हैं)। फिर right - 1 से रिकर्स। ३. अगर left == 0 और right == 0, रास्ता पूरी वैध शृंखला है। जोड़ दो।

बंद के लिए right > left क्यों? कुछ अक्षर रखने के बाद खुले रखे = न - left, बंद रखे = न - right। अगला बंद रखने से पहले बंद < खुले चाहिए, यानी न - right < न - left, जो right > left बन जाता है। वही इनवेरिएंट, अलग काउंटर।

इस्तेमाल हुई गिनती वाला वही आइडिया

कुछ लोग शून्य से openUsed और closeUsed रखते हैं:

( रखो अगर openUsed < न।
) रखो अगर closeUsed < openUsed।

वही पेड़। एक कहानी चुनो और उसी पर टिके रहो। नीचे बची गिनती है।

न = २ का पेड़

path="", left=2, right=2
  '(' → "(", 1, 2
    '(' → "((", 0, 2
      ')' → "(()", 0, 1
        ')' → "(())"  done
    ')' → "()", 1, 1
      '(' → "()(", 0, 1
        ')' → "()()"  done
      ')'  forbidden (right == left; close would break balance)
  ')'  forbidden at root (need right > left; here they are equal)

दो पत्ते: (()) और ()()। कोई रास्ता अवैध पूरी शृंखला पर नहीं खत्म होता।

गिनती: कैटलान संख्याएँ

न जोड़ों के लिए वैध शृंखलाओं की संख्या न-वीं कैटलान संख्या है:

C_n = (1 / (n + 1)) * (2n choose n)

न	सी_न
०	१
१	१
२	२
३	५
४	१४
५	४२

इंटरव्यू में यह बोलो। आउटपुट का आकार कैटलान है, २^(२न) या सी(२न, न) नहीं।

बिल्डर का चुनाव

मौजूदा रास्ते के लिए StringBuilder: जोड़ो, रिकर्स करो, आखिरी अक्षर मिटाओ। हर पूरी उत्तर की लंबाई २न।

४. जावा हल

import java.util.ArrayList;
import java.util.List;

/**
 * Generate all valid strings of n pairs of parentheses.
 * Backtracking with remaining open and close counts.
 */
public class Parens {

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n < 0) {
            return result;
        }
        backtrack(n, n, new StringBuilder(), result);
        return result;
    }

    /**
     * @param left  remaining '(' you may still place
     * @param right remaining ')' you may still place
     */
    private void backtrack(int left, int right, StringBuilder path, List<String> result) {
        if (left == 0 && right == 0) {
            result.add(path.toString());
            return;
        }

        if (left > 0) {
            path.append('(');
            backtrack(left - 1, right, path, result);
            path.deleteCharAt(path.length() - 1);
        }

        // Only close when more opens are already on the path than closes.
        // Equivalent: remaining closes strictly exceed remaining opens.
        if (right > left) {
            path.append(')');
            backtrack(left, right - 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

चाल: न = ३

शुरुआत left = 3, right = 3, रास्ता खाली।

१. पहले खुला ही: "(", left २, right ३। २. वहाँ से खोल या बंद (right > left) कर सकते हो। कानूनी मिश्रण से शाखाएँ बढ़ती हैं। ३. पत्ते (एक डेप्थ-फ़र्स्ट क्रम में):

((()))
(()())
(())()
()(())
()()()

पाँच शृंखलाएँ। सी_३ = ५ से मेल खाता है।

वैकल्पिक: इस्तेमाल गिनती वाला रूप

वही नियंत्रण प्रवाह, अलग पैरामीटर:

private void backtrack(int n, int openUsed, int closeUsed, StringBuilder path, List<String> result) {
    if (path.length() == 2 * n) {
        result.add(path.toString());
        return;
    }
    if (openUsed < n) {
        path.append('(');
        backtrack(n, openUsed + 1, closeUsed, path, result);
        path.deleteCharAt(path.length() - 1);
    }
    if (closeUsed < openUsed) {
        path.append(')');
        backtrack(n, openUsed, closeUsed + 1, path, result);
        path.deleteCharAt(path.length() - 1);
    }
}

कॉल: backtrack(n, 0, 0, new StringBuilder(), result)। इंटरव्यू में एक ही रूप रखो ताकि असमानता न उलझे।

धुआँ टेस्ट

Parens p = new Parens();

assert p.generateParenthesis(0).equals(List.of(""));
assert p.generateParenthesis(1).equals(List.of("()"));

List<String> two = p.generateParenthesis(2);
assert two.size() == 2;
assert two.contains("(())") && two.contains("()()");

List<String> three = p.generateParenthesis(3);
assert three.size() == 5;
assert three.contains("((()))");
assert three.contains("(()())");
assert three.contains("(())()");
assert three.contains("()(())");
assert three.contains("()()()");

assert p.generateParenthesis(4).size() == 14;

५. जटिलता तालिका

मान लो सी_न न-वीं कैटलान संख्या है (परिणामों की गिनती)।

हिस्सा	लागत	नोट
परिणाम गिनती	`सी_न`	लगभग `४^न / (न^(३/२) √π)` असिम्प्टोटिक
हर परिणाम की लंबाई	`२न`	स्थिर
सब बनाने का काम	ओ(सी_न · न) शैली	हर वैध शृंखला लंबाई २न का रास्ता; अंदरूनी नोड उपसर्ग बाँटते हैं
रिकर्शन गहराई	ओ(न)	ज़्यादा से ज़्यादा २न फ्रेम, रास्ता ≤ २न
अतिरिक्त जगह	ओ(न) स्टैक + रास्ता	आउटपुट सूची के अलावा
आउटपुट जगह	ओ(सी_न · न)	हर शृंखला रखना ज़रूरी

आउटपुट आकार से तेज़ पूरी सूची नहीं बना सकते। फायदा यह है कि जो उपसर्ग पहले ही संतुलन तोड़ चुका, उसे छूते ही नहीं। सभी सी(२न, न) बनाकर फिर छानना अवैध पूरी शृंखलाओं का भी खर्च लेता है।

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर यहाँ चुभोते हैं:

न = ० → एक खाली शृंखला (अगर वही बेस केस है)।
न = १ → सिर्फ "()"।
ऋणात्मक न → खाली सूची; अनंत रिकर्स मत करो।
बड़ा न → सी_१० = १६७९६, सी_१५ पहले से बड़ा। पैमाने पर पूछें तो कैटलान वृद्धि बताओ।
सिर्फ लंबाई २न इकट्ठा करो → बेस केस और दोनों काउंटर शून्य भूलो तो परिणाम छूटते हैं या अटक जाते हो।

आम गलतियाँ:

१. right > 0 होते ही ) अनुमति। इससे )( उपसर्ग आ जाते हैं। चाहिए right > left (बची) या closeUsed < openUsed (इस्तेमाल)। २. अनडू भूलना (deleteCharAt)। भाई शाखाएँ गंदा बिल्डर बाँटती हैं। ३. सभी सी(२न, न) पैटर्न बनाकर स्टैक से जाँचना। सही है पर धीमी कहानी; बनाते समय काटना आगे रखो। ४. डुप्लिकेट हटाने के लिए सेट। साफ काउंटर के साथ हर कदम एक तय अक्षर रखे तो डुप्लिकेट नहीं बनने चाहिए। ५. न जोड़े बनाम न अक्षर पर ऑफ-बाय-वन। कुल लंबाई २न है, न नहीं। ६. सिर्फ प्रिंट, रिटर्न वैल्यू नहीं। जटिलता और टेस्ट साफ हों तो सूची बेहतर।

मिलती-जुलती समस्याएँ जो उलझती हैं:

एक शृंखला जाँचना: स्टैक या काउंटर, ओ(न)। यह समस्या नहीं।
सबसे लंबी वैध उपशृंखला: डायनामिक प्रोग्रामिंग या स्टैक। अलग।
कई प्रकार के कोष्ठक नेस्टिंग नियमों के साथ: वैसा ही बैकट्रैक, ज़्यादा चिह्न।

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

कोष्ठक बनाना, इंटरव्यू संस्करण:

१. न ( और न ) वाली हर शृंखला चाहिए जो संतुलन कभी ऋणात्मक न करे और अंत में शून्य पर आए। २. बाएँ से दाएँ बनाओ। कितने खुले और बंद अभी रख सकते हो (या कितने पहले रख चुके) ट्रैक करो। ३. खुले बचे हों तो ( रखो। ४. ) तभी रखो जब नया बंद पहले लिखे खुले से आगे न निकले। ५. दोनों बची गिनती शून्य हों तो शृंखला जोड़ो। ६. उत्तरों की गिनती न-वीं कैटलान है: १, १, २, ५, १४, ... ७. परम्युटेशन जैसा ही बैकट्रैक कंकाल: चुनो, रिकर्स, अनडू। कानूनी फिल्टर संतुलन का नियम है।

अगर न = २ का पेड़ दो पत्तियों के साथ खींच सको और बता सको कि आगे का ) क्यों मना है, समस्या ८.९ तुम्हारी है। आगे पेंट फिल: दूसरे रिकर्सिव घूमने से एक क्षेत्र भरना।