การจัดข้อความให้เหมาะสมใน C++

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

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

ดังนั้นหากอินพุตเป็นแบบ

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

• สร้างอาร์เรย์ที่เรียกว่าผลลัพธ์

• สำหรับฉันในช่วง 0 ถึงขนาด a ให้อัปเดต i โดย j

  • ความกว้าง :=0

  • สำหรับ j ในช่วง i ถึงขนาดของ a และ ความกว้าง + ขนาดของ a[j] + j – i <=b,

    • width :=width + size ของ a[j]

  • ช่องว่าง :=1, พิเศษ :=0

  • ถ้า j – 1 !=1 และ j !=ขนาดของ a แล้ว

    • space :=(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) จำนวนช่องว่างด้วยบรรทัด

  • แทรกบรรทัดลงในผลลัพธ์

• ผลตอบแทน

ตัวอย่าง

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

#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 = {"I", "love", "coding.", "here", "we", "will", "write", "some", "program"};
   Solution ob;
   print_vector(ob.fullJustify(v, 16));
}

อินพุต

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

ผลลัพธ์

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