C++でテキストの両端揃え（ジャスティフィケーション）を実装する方法

単語の配列と最大幅 maxWidth が与えられたとき、各行がちょうど maxWidth 文字になるようにテキストを整形し、両端を揃える（フル・ジャスティファイ）ことを考えます。単語は貪欲法（グリーディーなアプローチ）で詰め込みます。つまり、1行にできるだけ多くの単語を収め、必要に応じて余分なスペース「 」を補って、各行の文字数をちょうど maxWidth に合わせます。

単語間の余分なスペースは、できるだけ均等に分配します。行内のスペース数が単語間で均等に割り切れない場合は、左側の空きスロットに右側よりも多くのスペースを割り当てます。また、テキストの最終行は左揃えとし、単語間に余分なスペースは挿入しません。

例えば、入力が次のような場合を考えてみましょう。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

• 結果を格納する配列 result を作成する
• i を 0 から配列 a のサイズまで、i を j で更新しながら繰り返す
  • width := 0
  • j を i から配列 a のサイズまで、かつ width ＋ a[j] のサイズ ＋ j − i ≦ b の間、j を更新しながら繰り返す
    • width := width ＋ a[j] のサイズ
  • space := 1、extra := 0
  • j − i ≠ 1 かつ j ≠ 配列 a のサイズの場合
    • space := (b − width) ÷ (j − i − 1)
    • extra := (b − width) mod (j − i − 1)
  • line := a[i]
  • k を i ＋ 1 から j まで繰り返す
    • line に space 個の空白を連結する
    • extra ＞ 0 の場合、さらに空白を1つ連結する
    • extra を 1 減らす
    • line := line ＋ a[k]
  • x := line のサイズ
  • line := line ＋ (b − x) 個の空白
  • line を result に挿入する
• result を返す

実装例

理解を深めるために、以下の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 = {"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 ,
]

出力を見ると、各行がちょうど16文字になるようにスペースが調整されていることがわかります。最終行の「program」は左揃えで処理され、行の幅を満たすために右側が空白で埋められています。このように、貪欲法で単語を行に詰め込み、残りの余白を単語間に均等に分配することで、美しい両端揃えのテキスト整形が実現できます。