Zigzag Conversion(M,String)

https://leetcode.com/problems/zigzag-conversion/description/

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

1. Python 

 

개어렵다..

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # numRows*2-2
        dic = {}
        for i in range(numRows):
            dic[i] = ""

        while s:
            for j in range(numRows):
                dic[j] += s[j]
            s = s[numRows:]
            if s:
                for k in range(numRows-2):
                    dic[numRows-2-j] = s[k]
                s = s[numRows-2:]
        ans = ""
        for x in dic:
            ans += dic[x]
        return ans

이까지 적다가 포기..

 

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows ==1 or numRows >= len(s) : return s

        idx = 0
        d = 1
        rows = [[] for x in range(numRows)]
        
        for c in s:
            rows[idx].append(c)
            if idx == 0:
                d=1
            elif idx == numRows - 1:
                d=-1           
            idx += d
        
        for i in range(numRows):
            rows[i] = ''.join(rows[i])
        
        return ''.join(rows)

 

Solution을 보니까 경의로운 영역이다. 어려운 Function은 하나도 없다.

단지 내 경험치가 부족했을뿐 ㅜ ㅜ이건 진짜 수학문제 푸는 거랑 큰 차이가 없다..

 

2. C

 

C로는 도저히 불가할 거 같아서 pass

 

    if (numRows == 1 || numRows >= strlen(s)) {
        return strdup(s);  // 문자열을 그대로 반환
    }

    int len = strlen(s);
    char** rows = (char**)malloc(numRows * sizeof(char*));
    for (int i = 0; i < numRows; i++) {
        rows[i] = (char*)calloc(len + 1, sizeof(char));  // 각 행을 초기화
    }

    int current_row = 0;
    int going_down = 0;

    for (int i = 0; i < len; i++) {
        strncat(rows[current_row], &s[i], 1);  // 현재 행에 문자 추가
        if (current_row == 0 || current_row == numRows - 1) {
            going_down = !going_down;  // 방향 전환
        }
        current_row += going_down ? 1 : -1;
    }

    char* result = (char*)calloc(len + 1, sizeof(char));
    for (int i = 0; i < numRows; i++) {
        strcat(result, rows[i]);  // 모든 행을 연결
        free(rows[i]);  // 메모리 해제
    }
    free(rows);

    return result;

gpt 코드 참고..

 

 

3. C++

 

class Solution {
public:
    string convert(string s, int numRows) {
        if(s.length()<=numRows || numRows == 1) return s;

        vector<vector<char>> vec(numRows);

        int idx = 0;
        int d = 1;

        for(char c : s){
            vec[idx].push_back(c);
            if(idx==0){
                d = 1;
            }
            else if(idx==numRows-1){
                d = -1;
            }
            idx += d;
        }
        string result;
        for(const auto &x : vec){
            for(const char &c1 : x){
                result += c1;
            }
        }
        return result;
    }
};

 

Python과 같은 logic으로 해결!