[LeetCode] [Medium] ZigZag Conversion
2021. 3. 21. 14:56ㆍ알고리즘/LeetCode
1. Problem
"PAYPALISHIRING" => "PAHNAPLSIIGYIR"
Given a string and row of zigzag pattern.
return a zigzag pattern string for line by line.
2. Sol1
store in order => each row a vector.
and sum all vector 0~numRows-1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public:
string convert(string s, int numRows) {
if(numRows == 1)
return s;
vector<string> answer(numRows, "");
string ret = "";
int converti = 0;
bool isDown = true;
for(int i = 0; i < s.size(); i++)
{
answer[converti] += s[i];
if(converti == 0)
isDown = true;
else if(converti == numRows-1)
isDown = false;
if(isDown)
converti++;
else
converti--;
}
for(int i = 0; i < numRows; i++)
ret += answer[i];
return ret;
}
|
cs |
3. Sol2
zigzag pattern
if row is not 0 or numRows -1
all next elemental in row repeat up & down.
if row is 0 everytime down
if row is numRow-1 everytime up.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public:
string convert(string s, int numRows) {
if(numRows == 1)
return s;
int converti = 0, sSize = s.size(), i = 0;
bool isDown;
string ret(sSize, 0);
for(int row = 0; row < numRows ; row++)
{
converti = row;
isDown = true;
while(converti < sSize)
{
ret[i] = s[converti];
if(isDown)
{
isDown = false;
if(row == numRows-1) continue;
converti += 2*(numRows-1 - row);
}
else
{
isDown = true;
if(row == 0) continue;
converti += 2*row;
}
i++;
}
}
return ret;
}
};
|
cs |
'알고리즘 > LeetCode' 카테고리의 다른 글
| [LeetCode] [C++] Reverse Integer (0) | 2021.05.11 |
|---|---|
| [LeetCode] [Medium] Longest Palindromic Substring (dp) (0) | 2021.03.20 |
| [LeetCode] [Medium] Longest Substring Without Repeating Characters (0) | 2021.03.18 |
| [LeetCode] [Medium] Add Two Numbers (linked list) (0) | 2021.03.17 |
| [LeetCode] [easy] Two Sum (brute-force, map) (0) | 2021.03.16 |