blob: 836b1964d4ab25a9057f65b993b9c0ddb8a86ff9 (
plain)
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
// 6. Zigzag Conversion
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* the string "PAYPALISHIRING" is written in zigzag pattern on a given number
* of rows like this:
* P A H N
* A P L S I I G
* Y I R
* and then read line by line: "PAHNAPLSIIGYIR". write function that will take
* a string and mak this conversion give a number of rows.
*/
char *convert(char *s, int numRows) {
const int len = strlen(s);
if (numRows == 1 || len == 1)
return s;
int sub_len;
if (numRows == 2)
sub_len = len / 2 + len % 2;
else
sub_len = len / (numRows - 1);
int *id = calloc(numRows, sizeof(int));
char **substr = malloc(numRows * sizeof(char *));
for (int i = 0; i < numRows; i++)
substr[i] = malloc((sub_len + 1) * sizeof(char));
substr[0][0] = s[0];
id[0] = 1;
int state = 1, pos;
while (state < len) {
// down
for (int i = 1; i < numRows && state < len; i++) {
pos = id[i];
substr[i][pos] = s[state];
state++;
id[i]++;
}
// up
for (int i = numRows - 2; i >= 0 && state < len; i--) {
pos = id[i];
substr[i][pos] = s[state];
state++;
id[i]++;
}
}
pos = 0;
for (int i = 0; i < numRows; i++) {
strncpy(&s[pos], substr[i], id[i]);
pos += i;
}
for (int i = 0; i < numRows; i++)
free(substr[i]);
free(substr);
free(id);
return s;
}
int main() {
char s1_2[] = "PAYPALISHIRING", s3[] = "A";
printf("%s\n", convert(s1_2, 3)); // expect: PAHNAPLSIIGYIR
printf("%s\n", convert(s1_2, 4)); // expect: PINALSIGYAHRPI
printf("%s\n", convert(s3, 1)); // expect: A
}
|