โปรแกรมเพื่อปรับชุดคำโดยแปลงเป็นบรรทัดยาวเดียวกันใน C++

สมมติว่าเรามีรายการคำและความกว้าง k เราต้องจัดเรียงข้อความเพื่อให้แต่ละบรรทัดมีจำนวนอักขระ k ตัวพอดี และข้อความได้รับการปรับให้เหมาะสม ที่นี่เราจะบรรจุคำศัพท์ของเราให้มากที่สุดเท่าที่เราจะสามารถแทรกในแต่ละบรรทัด และเราจะใส่ช่องว่างพิเศษ ' ' เมื่อจำเป็น เพื่อให้แต่ละบรรทัดมีอักขระ k ตัวพอดี

ช่องว่างเพิ่มเติมระหว่างคำควรกระจายให้เท่าๆ กันมากที่สุด ถ้าจำนวนช่องว่างบนบรรทัดไม่แบ่งเท่า ๆ กันระหว่างคำ ช่องว่างทางด้านซ้ายจะได้รับการกำหนดช่องว่างมากกว่าช่องทางด้านขวา สำหรับบรรทัดสุดท้ายของข้อความ ควรปล่อยให้ชิดขอบและไม่เว้นวรรคระหว่างคำ

ดังนั้นหากอินพุตเป็นเหมือน ["The", "grumpy", "wizards", "make", "toxic", "brew", "for", "the", "evil", "queen", "and" , "แจ็ค"] และ k =13

แล้วผลลัพธ์จะเป็น −

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างอาร์เรย์ที่เรียกว่าผลลัพธ์
• สำหรับฉันในช่วง 0 ถึงขนาด a ให้อัปเดต i โดย j
  • ความกว้าง :=0
  • สำหรับ j ในช่วง i ถึงขนาดของ a และ ความกว้าง + ขนาดของ a[j] + j – i <=b,
    • ความกว้าง :=ความกว้าง + ขนาดของ a[j]
  • ช่องว่าง :=1, พิเศษ :=0
  • ถ้า j – 1 !=1 และ j !=ขนาดของ a แล้ว
    • ช่องว่าง :=(b - width) / j – i – 1
    • พิเศษ :=(b - width) mod (j – i – 1)
  • line :=a[i]
  • สำหรับ k ในช่วง i + 1 ถึง j
    • เชื่อมจำนวนช่องว่างของช่องว่างด้วยบรรทัด
    • ถ้าพิเศษ> 0 ให้ต่อช่องว่างกับบรรทัด
    • ลดเพิ่มอีก 1
    • line :=เชื่อม a[k] กับ line
  • x :=ขนาดของเส้น
  • line :=concatenate (b - x) จำนวนช่องว่างด้วยบรรทัด
  • แทรกบรรทัดลงในผลลัพธ์
• ผลตอบแทน

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   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;
   }
};
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 ,]