📗Z字形変換アルゴリズム問題集第一天

難易度：中#

問題：#

与えられた文字列 s を、与えられた行数 numRows に基づいて、上から下、左から右に Z 字形に配置します。

例えば、入力文字列が "PAYPALISHIRING" で、行数が 3 の場合、配置は次のようになります：

P A H N
A P L S I I G
Y I R
その後、出力は左から右に行ごとに読み取って、新しい文字列を生成します。例えば："PAHNAPLSIIGYIR"。

指定された行数に従って文字列を変換する関数を実装してください：

string convert(string s, int numRows);

例：#

例 1：

入力：s = "PAYPALISHIRING", numRows = 3
出力："PAHNAPLSIIGYIR"
例 2：

入力：s = "PAYPALISHIRING", numRows = 4
出力："PINALSIGYAHRPI"
説明：
P I N
A L S I G
Y A H R
P I
例 3：

入力：s = "A", numRows = 1
出力："A"

解析：#

個人解析：#

逆 Z を正 Z に反転させ、二次元文字列配列を使って記録します（後に証明されるように、二次元文字列配列は文字列型リストで直接置き換え可能です）。
遍歴は二つの方向があり、一つは i を固定して j++、もう一つは i++、j--（後に公式解法では flag=1、-1 を使ってこの二つの状態を表現し、より優雅になります）。

公式解析：#

文字列 s は Z 字形で順序付けられた文字列で、目標は行ごとに印刷することです。

numRows 行の文字列を s1 , s2 , … , s**n とすると、順に文字列 s を遍歴する際、各文字 c が N 字形に対応する 行インデックス は s1 から s**n に増加し、その後 s**n から s1 に減少します…… このように繰り返します。

したがって解決策は：この行インデックスの変化をシミュレートし、s を遍歴する中で各文字を正しい行 res[i] に填入します。

アルゴリズムの流れ：#

順に文字列 s を遍歴します：

res[i] += c： 各文字 c を対応する行 s**i に填入します；
i += flag： 現在の文字 c に対応する行インデックスを更新します；
flag = - flag： Z 字形の転換点に達した時、反転を実行します。

コード：#

[Python]

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return "".join(res)

[Java]

class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}

[C++]

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows < 2)
            return s;
        vector<string> rows(numRows);
        int i = 0, flag = -1;
        for (char c : s) {
            rows[i].push_back(c);
            if (i == 0 || i == numRows -1)
                flag = - flag;
            i += flag;
        }
        string res;
        for (const string &row : rows)
            res += row;
        return res;
    }
};

複雑度分析：#

時間複雑度 *O*(*N*) ：文字列 s を一度遍歴します；
空間複雑度 *O*(*N*) ：各行の文字列が合計で O(N) の追加空間を占めます。

個人コード：#

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        ArrayList<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        int flag = -1;
        int i = 0;
        for (char c : s.toCharArray()) {
            if (i == 0 || i == numRows - 1) {
                flag = -flag;
            }
            rows.get(i).append(c);
            i += flag;
        }

        StringBuilder res = new StringBuilder();
        rows.forEach(e->res.append(e));
        return res.toString();
    }
}