LeetCode - Medium - 6. ZigZag Conversion

深碍√TFBOYSˉ_ 2023-01-01 00:55 91阅读 0赞

## Topic ##

*  String

## Description ##

[https://leetcode.com/problems/zigzag-conversion/][https_leetcode.com_problems_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

**Example 3**:

Input: s = "A", numRows = 1
    Output: "A"

**Constraints**:

*  1 <= s.length <= 1000
 *  `s` consists of English letters (lower-case and upper-case), ‘,’ and ‘.’.
 *  1 <= numRows <= 1000

## Analysis ##

分析Example 2，Input: s = “PAYPALISHIRING”, numRows = 4

3           3
    group     2   2       2   2
            1       1   1        1     1
          0           0             0
    index 0 1 2 3 4 5 6 7 8 9 10 11 12 13
      s   P A Y P A L I S H I R  I  N  G

按group号，分别收集字符，最后到汇总输出。

## Submission ##

public class ZigZagConversion { 
    	public String convert(String s, int numRows) { 
    		StringBuilder[] sbs = new StringBuilder[numRows];
    
    		boolean upDownflag = true;
    		int sbsPointer = 0;
    		int halfCycle = numRows - 1;
    
    		for (int i = 0; i < s.length(); i++) { 
    			if (sbs[sbsPointer] == null)
    				sbs[sbsPointer] = new StringBuilder();
    
    			sbs[sbsPointer].append(s.charAt(i));
    
    			if (halfCycle != 0) { 
    				if (upDownflag && sbsPointer + 1 > halfCycle) { 
    					upDownflag = false;
    				}
    				if (!upDownflag && sbsPointer - 1 < 0) { 
    					upDownflag = true;
    				}
    				sbsPointer = upDownflag ? sbsPointer + 1 : sbsPointer - 1;
    			}
    		}
    
    		for (int i = 1; i < numRows; i++) { 
    			if (sbs[i] == null)
    				break;
    			sbs[0].append(sbs[i]);
    		}
    
    		return sbs[0].toString();
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class ZigZagConversionTest { 
    
    	@Test
    	public void test() { 
    		ZigZagConversion obj = new ZigZagConversion();
    
    		assertEquals("PAHNAPLSIIGYIR", obj.convert("PAYPALISHIRING", 3));
    		assertEquals("PINALSIGYAHRPI", obj.convert("PAYPALISHIRING", 4));
    		assertEquals("A", obj.convert("A", 1));
    		assertEquals("AB", obj.convert("AB", 1));
    		
    	}
    }

[https_leetcode.com_problems_zigzag-conversion]: https://leetcode.com/problems/zigzag-conversion/