## LeetCode-ZigZag conversion 原

52iSilence7

### Zigzag Conversion

``````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);
Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

### Solution

``````package com.dylan.leetcode;

import org.junit.Assert;
import org.junit.Test;

/**
* Created by liufengquan on 2018/7/4.
*/
public class ZigZagConversion {
public String convert(String s, int numRows) {
if (numRows <= 1 || s.length() <= numRows) {
return s;
}
int split = numRows + numRows - 2;
int group = s.length() / split;
group = s.length() % split == 0 ? group : group + 1;
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < split / 2 + 1; i++) {//走到中间
for (int j = 0; j < group; j++) {
int begin = j * split + i;
if (begin < s.length()) {
stringBuilder.append(s.charAt(begin));
}
int mirror = begin + (numRows - 1 - i) * 2;
if (mirror != (j + 1) * split//不越界group
&& mirror != begin//不重复
&& mirror < s.length()) {//不越界
stringBuilder.append(s.charAt(mirror));
}
}
}
return stringBuilder.toString();
}

@Test
public void test() {
Assert.assertTrue("PAHNAPLSIIGYIR".equals(convert("PAYPALISHIRING", 3)));
Assert.assertTrue("PINALSIGYAHRPI".equals(convert("PAYPALISHIRING", 4)));
}
}

``````

### mind path

We can notice that it has a pattern. Every zigzag pattern is composed by a list of `L` structures. As of example 2,

``````P
A   L  is one `L` structure
Y A
P

I
S  I  is another `L` structure
H R
I

N
G is an uncompeleted `L` structure.

``````

Let's write the zigzag position down.Assume numRows = 4

``````string  : P A H N A P L S I I G Y I R
position: 0 1 2 3 4 5 6 7 8 9 a b c d
zig pos:  0 1 2 3 2 1 0 1 2 3 2 1 0 1
``````

Every `L` structure has `split = numRows + numRows - 2` elements. Total `group = s.length()/split; group = s.length() % split == 0 ? group : group + 1;` groups. Then we extract all chars at pos 0, all chars at pos 1, all chars at pos 2 etc. We get the result string.

### 52iSilence7

[leetcode] ZigZag Conversion

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 ......

jdflyfly
2014/06/24
72
0
Leetcode 6. ZigZag Conversion

SnailTyan
2018/09/17
0
0
6. ZigZag Conversion - LeetCode

LeetCode Problems Solutions question description: 问题描述 //问题截图： origin.png //锯齿状 sawtooth.png Thinking 你们可以自己先考虑一下。 solution with java - Java解决方案 solu......

2017/08/23
0
0
LeetCode - ZigZagConversion

Mock2052
2017/11/21
0
0
Leetcode_6. Zigzag convertion

6. Zigzag convertion 对输入的字符串做锯齿形变换，并输出新的字符串，所谓zigzag变化如下图所示。 将"ABCDEFGHIJKL"做4行的锯齿变换，新的字符串为：AGBFHLCEIKDJ" 实现一个根据输入字符串...

gexin1023
2018/06/28
0
0

6分钟前
3
0

9分钟前
5
0
Yii 框架中rule规则必须搭配验证函数才能使用

public \$store_id;public \$user_id;public \$page;public \$limit;public \$list;public \$mch_list;public \$cart_id;public \$is_community;public \$shop_id;public \$cart_typ......

chenhongjiang
11分钟前
2
0
Flutter使用Rammus实现阿里云推送

EmilyWu
12分钟前
26
0
Knative 实战：三步走！基于 Knative Serverless 技术实现一个短网址服务

27分钟前
2
0