C++ में शब्दों के सेट को समान लंबाई की लाइनों में बदलकर जस्टिफाई करने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास शब्दों की एक सूची और एक चौड़ाई k है, हमें टेक्स्ट को इस तरह व्यवस्थित करना है कि प्रत्येक लाइन में ठीक k संख्या में कैरेक्टर हों और टेक्स्ट पूरी तरह से जस्टिफाई हो। यहां हम प्रत्येक लाइन में जितने शब्द डाल सकते हैं उतने डालेंगे। और जब आवश्यक हो तो अतिरिक्त स्पेस ' ' पैड करेंगे ताकि प्रत्येक लाइन में ठीक k कैरेक्टर हों।

यहां शब्दों के बीच अतिरिक्त स्पेस को यथासंभव समान रूप से वितरित किया जाना चाहिए। यदि एक लाइन पर स्पेस की संख्या शब्दों के बीच समान रूप से विभाजित नहीं होती है, तो बाएं तरफ के खाली स्लॉट को दाएं तरफ के स्लॉट की तुलना में अधिक स्पेस असाइन किए जाएंगे। टेक्स्ट की अंतिम लाइन के लिए, यह लेफ्ट जस्टिफाई होनी चाहिए और शब्दों के बीच कोई अतिरिक्त स्पेस नहीं डाला जाना चाहिए।

उदाहरण के लिए, यदि इनपुट है ["The", "grumpy", "wizards", "make", "toxic", "brew", "for", "the", "evil", "queen", "and", "Jack"], और k = 13, तो आउटपुट होगा:

The grumpy wizards make toxic brew for the evil queen and Jack

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

1. result नामक एक ऐरे बनाएं
2. i को 0 से a के आकार तक, i को j से अपडेट करते हुए:
   • width := 0
   • j को i से a के आकार तक और width + a[j] का आकार + j - i <= b तक:
     • width := width + a[j] का आकार
   • space := 1, extra := 0
   • यदि j - i != 1 और j != a का आकार, तो:
     • space := (b - width) / (j - i - 1)
     • extra := (b - width) % (j - i - 1)
   • line := a[i]
   • k को i+1 से j तक:
     • space संख्या में ब्लैंक-स्पेस को line के साथ जोड़ें
     • यदि extra > 0, तो line के साथ स्पेस जोड़ें
     • extra को 1 से घटाएं
     • line := a[k] को line के साथ जोड़ें
   • x := line का आकार
   • line := (b - x) संख्या में स्पेस को line के साथ जोड़ें
   • line को result में डालें
3. res वापस करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> fullJustify(vector<string>& a, int b) {
        vector<string> result;
        int i, j;
        for (i = 0; i < a.size(); i = j) {
            int width = 0;
            for (j = i; j < a.size() && width + a[j].size() + j - i <= b; j++) {
                width += a[j].size();
            }
            int space = 1;
            int extra = 0;
            if (j - i != 1 && j != a.size()) {
                space = (b - width) / (j - i - 1);
                extra = (b - width) % (j - i - 1);
            }
            string line(a[i]);
            for (int k = i + 1; k < j; k++) {
                line += string(space, ' ');
                if (extra-- > 0) {
                    line += " ";
                }
                line += a[k];
            }
            int x = line.size();
            line += string(b - x, ' ');
            result.push_back(line);
        }
        return result;
    }
};

int main() {
    vector<string> v = {"The", "grumpy", "wizards", "make", "toxic", "brew", "for", "the", "evil", "queen", "and", "Jack"};
    Solution ob;
    print_vector(ob.fullJustify(v, 13));
}

इनपुट

["I", "love", "coding.", "here", "we", "will", "write", "some", "program"] 16

आउटपुट

[The grumpy, wizards make, toxic brew, for the evil, queen and, Jack ,]