LeetCode: ZigZag Conversion

Easy問題ばかり解いていたので、たまにはMedium問題を解きます。

問題

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

解答

本問題では、sの中での何文字目がジグザグの何行目に来るのかを知る必要がありそうです。

とはいえ、いまいち掴みどころがわかりません。 そこで手を動かて試してみることにします。

  1. numRows = 1 の時

これはsが返ってきますね。

  1. s.length <= numRows の時

これも1.と同様にsが返ってきますね。

  1. numRows < s.length の時

主に考えないといけないのはこの場合です。与えられている例題で少し考えてみます。

3-1. s = "PAYPALISHIRING", numRows = 3の時

実際の値 sの中で何文字目 ジグザグの何行目
P 1 1
A 2 2
Y 3 3
P 4 2
A 5 1
L 6 2
I 7 3
S 8 2
H 9 1
I 10 2
R 11 3
I 12 2
N 13 1
G 14 2

なるほど、そういうことですね。 ひとまず実装の戦略が何となく立ちましたが、もう一つの例題でも確認してみます。

3-1. s = "PAYPALISHIRING", numRows = 4の時

実際の値 sの中で何文字目 ジグザグの何行目
P 1 1
A 2 2
Y 3 3
P 4 4
A 5 3
L 6 2
I 7 1
S 8 2
H 9 3
I 10 4
R 11 3
I 12 2
N 13 1
G 14 2

なるほど、やはりそうですね。

上2つの表で注目して欲しいのは右端の列です。

数字がそれぞれ 1, 2, 3, 2, 1, 2, 3, 2, 1, ...1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1, ...と周期的に並んでいますね。

これがつまりどういうことかというと、3-1.の時、11 + 4 * n 番目(nは非負整数)、2偶数番目3は...というように規則的に数字が現れるということです。(3-2.の時はもう少し複雑な規則になりますが、基本的には同じことです。)

以上の考察から、sの中での何文字目がジグザグの何行目に来るかがわかったので、あとは実装するのみです。

public class Solution {
  public String convert(String s, int numRows) {
    if (numRows <= 1 || s.length() <= numRows) {
      return s;
    }
    char[] ans = new char[s.length()];
    int current = 0;
    for (int i = 0; i < numRows; i++) {
      int patterNum = 2 * numRows - 2;
      int intervalNum = 2 * (numRows - i) - 2;
      for (int j = i; j < s.length(); j += patterNum) {
        ans[current] = s.charAt(j);
        current++;
        if (i != 0 && i != numRows - 1  && j + intervalNum < s.length()) {
          ans[current] = s.charAt(j + intervalNum);
          current++;
        }
      }
    }
    return String.valueOf(ans);
  }
}

(sの長さをm、numRowsをnした時)時間計算量:O(m x n)、メモリ計算量:O(m)

この解法は結構速い方みたいですね。(どんぐりの背比べですが。) f:id:tsukakei1012:20181128142150p:plain

それでは他の人の解答も見てみます。

class Solution {
        public String convert(String s, int numRows) {
        char[] result = new char[s.length()];
        int count = 0;
        if(numRows == 1)return s;
        // 1行目の文字を埋めている
        for(int j = 0 ; j < s.length(); j += (numRows - 1) * 2)
            result[count++] = s.charAt(j);
        
        // 2 ~ numRows-1行目の文字を埋めている
        for(int i = 1 ; i < numRows - 1 ; i++) {
            int j = i;
            int add = (numRows - 1) * 2 - 2 * j;
                // i 行目の文字を埋めている処理
            while(j < s.length()) {
                result[count++] = s.charAt(j);
                j += add;
                add = (numRows - 1) * 2 - add;
            }
        }
        // numRows行目の文字を埋めている     
        for(int j = numRows - 1 ; j < s.length(); j += (numRows - 1) * 2)
            result[count++] = s.charAt(j);
        return String.copyValueOf(result);
        }
}

少しわかりづらいので、コメントを入れました。 2 ~ numRows-1行目の文字の埋め方が少し違いますが、やっていることは基本的に同じですね。