[LeetCode6: Z-shape transformation]

1. Description of the topic

This topic: Arrange a given string in a zigzag shape, and get a new string during traversal.

1. Subject content

Arranges a given string s in a zigzag top-to-bottom, left-to-right order according to the given number of rows numRows .
For example, when the input string is "PAYPALISHIRING" and the number of lines is 3, the arrangement is as follows:
P A H N
A P L S I I G
Y I R
After that, your output needs to be read line by line from left to right, producing a new string like: "PAHNAPLSIGYIR".
Please implement this function that transforms a string with a specified number of lines:
string convert(string s, int numRows);
Original title link: https://leetcode.cn/problems/zigzag-conversion/

2. Examples

2. Solutions

Algorithm flow:

  • Traverse the original string and add each character to the corresponding "line";
  • When the turning point of the data flow is encountered, that is, the first line and the last line, the direction of the data flow is changed, which is achieved by setting a flag variable flag;
  • Update the "line" corresponding to the current character;

Among them, when the number of incoming rows rows=1, the original string can be directly returned, and the core code handles the case of rows>1.
See an example:
The red arrow indicates the direction of the data flow. When traversing the string, whenever the first or last line is encountered, the direction of the data flow changes once. The subscript of the line corresponding to the current character follows: 0,1,…, A loop of rows-1,…,1,0.
Here, i is used to control the row corresponding to the current character; j represents the subscript corresponding to the character in the traversal string; and flag is used to control the direction of the data flow, whenever i=0 or i=rows-1, it is taken from itself. Conversely, that is, flag=-flag.

1.Java code

public class ZConvert {
    public static String stringConvert(String str,int rows) {
        if(rows==1){
            return str;
        }
        List<StringBuilder> rowsStr=new ArrayList<StringBuilder>();  // Store the new content form row by row
        for(int n=0;n<rows;n++){
            rowsStr.add(new StringBuilder());
        }
        int i=0;  // Controls the line corresponding to the current character
        int flag=-1;  // Control data orientation when z-arrangement
        int j=0;  //Controls the character currently traversed
        while (j<str.length()){  // iterate over the string
        	// core code
            rowsStr.get(i).append(str.charAt(j));
            if(i==0||i==rows-1){
                flag=-flag;  // The first or last line of data flow direction is reversed
            }
            i+=flag;  // Update the subscript of the line corresponding to the current character
            
            j++;  //Update the subscript of the traversed character
        }

//        System.out.println(rowsStr.toString());

        StringBuilder newStr=new StringBuilder();  //Concatenate to get a new string
        for(int r=0;r<rows;r++){
            newStr.append(rowsStr.get(r).toString());
        }
        return newStr.toString();
    }

    public static void main(String[] args) {
        String str="PAYPALISHIRING";
        int rows=5;
        System.out.println(stringConvert(str,rows));
    }
}

2.Python code

'''
LeetCode6:Z Glyph transformation
'''


def str_convert(string,rows_num):
    if rows_num==1:
        return string
    rows_str=[]
    for i in range(0,rows_num):
        rows_str.append('')
    i=0
    flag=-1
    for c in string:
        rows_str[i]+=c
        if i==0 or i==rows_num-1:
            flag=-flag
        i+=flag
    new_str=''
    for item in rows_str:
        new_str+=item
    return new_str


if __name__=='__main__':
    s = "PAYPALISHIRING"
    rows = 5
    print(str_convert(s,rows))

Problem solving ideas reference solution: https://leetcode.cn/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/
I can only say that the big guy, the god guy, has been writing it for a long time and it is wrong. At the beginning, I have been looking for the pattern between the subscripts of the string elements, and people are split. Seeing the big guy's answer, it's just a slap in the face! !

Tags: Java Algorithm Python leetcode

Posted by liquorvicar on Thu, 13 Oct 2022 02:46:21 +0530