アルゴリズム1000本ノック #6. ZigZag Conversion

10134 ワード
データ構造 データ構造とアルゴリズム interview algorithm 文字列処理 algorithm テキストリンク

Problem

問題は LeetCode から拝借しておりますが, 例題を見る限りPaypalのインタビューにて出題された事があるのではと推測されます.

文字列 "PAYPALISHIRING" を３行のジグザグ状に羅列すると以下のようになる

P   A   H   N
A P L S I I G
Y   I   R

これを行ごとに読むと次のようになる: "PAHNAPLSIIGYIR"
同じ要領で, 元の文字列と行数を与えられた時にジグザグ状に羅列して行ごとに読んだ時の
文字列を出力する関数を記述せよ.

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) は "PAHNAPLSIIGYIR" を返却する.

Solution

example1

ジグザグに羅列したあとの各行を t0, t1, t1 と名付けると, 元々の文字列をジグザグ状 (t0, t1, t2, t1, t0, t1, ...) に格納していくとそれぞれの行は作成できることがすぐ分かります.

Python版コード:

class Solution(object):
    def convert(self, s, numRows):
        leng = len(s)
        if leng == 0:      return ''
        if numRows <= 0:   return ''
        elif numRows == 1: return s

        resRows = [''] * numRows

        i = 0
        resRowNum = 0
        step = 1
        while i < leng:
            resRows[resRowNum] += s[i]

            if (step == 1 and resRowNum == numRows - 1) or (step == -1 and resRowNum == 0):
                step = -1 * step

            resRowNum += step
            i += 1

        return ''.join(resRows)

計算量: O(M), 空間量: O(M) (Mは与えられた文字列の長さ).

Java版のコード:

public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        if (len == 0 || numRows == 0) return "";
        if (numRows == 1) return s;

        StringBuilder[] resRows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            resRows[i] = new StringBuilder();
        }

        int rowIdx = 0;
        int step = 1;
        for (int i = 0; i < len; i++) {
            resRows[rowIdx].append(s.charAt(i));
            if ((step == 1 && rowIdx == numRows - 1) || (step == -1 && rowIdx == 0)) {
                step = -1 * step;
            }
            rowIdx += step;
        }

        StringBuilder sb = new StringBuilder(resRows[0]);
        for (int i = 1; i < numRows; i++) {
            sb.append(resRows[i]);
        }

        return sb.toString();
    }