leetcode_rust/problems/p000_0xx/
p000_006.rs

1//! # Description
2//! 
3//! The string "PAYPALISHIRING" is written in a zigzag pattern on a given 
4//! number of rows like this: (you may want to display this pattern in a fixed 
5//! font for better legibility)
6//! 
7//! ```plain
8//! P   A   H   N
9//! A P L S I I G
10//! Y   I   R
11//! ```
12//! 
13//! And then read line by line: "PAHNAPLSIIGYIR"
14//! 
15//! Write the code that will take a string and make this conversion given a 
16//! number of rows:
17//! 
18//! string convert(string `s`, int `numRows`);
19//!  
20//! | Example 1 |
21//! | :-- |
22//! | Input: s = "PAYPALISHIRING", numRows = 3 |
23//! | Output: "PAHNAPLSIIGYIR" |
24//! 
25//! | Example 2 |
26//! | :-- |
27//! | Input: s = "PAYPALISHIRING", numRows = 4 |
28//! | Output: "PINALSIGYAHRPI" |
29//! 
30//! Explanation: 
31//! ```plain
32//! P     I    N 
33//! A   L S  I G 
34//! Y A   H R 
35//! P     I 
36//! ``` 
37//! 
38//! | Example 3 |
39//! | :-- |
40//! | Input: s = "A", numRows = 1 |
41//! | Output: "A" |
42//! 
43//! Constraints:
44//! - `1 <= s.length <= 1000`
45//! - `s` consists of English letters (lower-case and upper-case), ',' and '.'.
46//! - `1 <= numRows <= 1000`
47//! 
48//! Source: <https://leetcode.com/problems/zigzag-conversion/>
49
50////////////////////////////////////////////////////////////////////////////////
51
52/// Enum choosing algorithm for the solution
53pub enum Algorithm {
54    /// String stacks
55    STACK = 0,
56    /// Char 2D array
57    MATRIX = 1,
58}
59
60/// Get a ZigZag matrix using given string and column-first algorithm.
61///
62/// Two solutions available, use second argument to decide which to use.
63///
64/// # Arguments
65/// * `s` - original string to convert.
66/// * `n_rows` - total ROWs to layout the characters.
67///
68/// # Examples
69/// ```
70/// use leetcode_rust::problems::p000_0xx::p000_006::zigzag_conversion;
71/// let mut result_value = zigzag_conversion(String::from("PAYPALISHIRING"), 1, None);
72/// assert_eq!(result_value, String::from("PAYPALISHIRING"));
73/// result_value = zigzag_conversion(String::from("PAYPALISHIRING"), 2, None);
74/// assert_eq!(result_value, String::from("PYAIHRNAPLSIIG"));
75/// result_value = zigzag_conversion(String::from("PAYPALISHIRING"), 3, None);
76/// assert_eq!(result_value, String::from("PAHNAPLSIIGYIR"));
77/// ```
78pub fn zigzag_conversion(s: String, n_rows: i32, alg: Option<Algorithm>) -> String {
79    match alg.unwrap_or(Algorithm::STACK) {
80        Algorithm::MATRIX => convert_s1(s, n_rows as usize),
81        Algorithm::STACK => convert_s2(s, n_rows),
82    }
83}
84
85#[cfg(test)]
86#[test]
87fn test_zigzag_conversion() {
88    assert!(zigzag_conversion(String::from("PAPAL"), 1, None) == String::from("PAPAL"));
89}
90
91/// Compose a ZigZag matrix using row-first algorithm.
92///
93/// Note the given row count has been mapped to column count in argument
94///
95/// # Arguments
96/// * `s` - original string to convert.
97/// * `n_cols` - total ROWs to layout the characters.
98#[allow(unused_assignments)]
99fn convert_s1(s: String, n_cols: usize) -> String {
100    let mut cur_row = 0u16;
101    let mut cur_col = 0u16;
102    let mut n_rows = 1;
103
104    // Considering max string length 1_000 ASCII characters, minimum 1 column,
105    // max row count would be 1_000.
106    let mut arr = vec![0u8; n_cols * 1000];
107    let mut direction = 0; // 0 for GO, 1 for TURN
108    let mut conv_idx = 0usize;
109    while conv_idx < s.len() {
110        // Set value of current pos
111        arr[cur_row as usize * n_cols + cur_col as usize] = s.as_bytes()[conv_idx];
112        conv_idx += 1;
113        // Calculate next coordinate and direction
114        if cur_col == 0 {
115            if n_cols > 1 {
116                if direction == 1 {
117                    direction = 0;
118                }
119                cur_col += 1;
120            } else {
121                // Move to next row directly because only 1 column needed.
122                cur_row += 1;
123                n_rows += 1;
124            }
125        } else {
126            if direction == 0 {
127                if cur_col < n_cols as u16 - 1 {
128                    // Only move to the right
129                    cur_col += 1;
130                } else {
131                    // Last position, change direction and move to next row
132                    direction = 1;
133                    cur_col -= 1;
134                    cur_row += 1;
135                    n_rows += 1;
136                }
137            } else {
138                // Move to left and below
139                cur_col -= 1;
140                cur_row += 1;
141                n_rows += 1;
142            }
143        }
144    }
145
146    conv_idx = 0;
147    let mut output = vec![0u8; s.len()];
148    cur_row = 0;
149    cur_col = 0;
150    let mut str_idx = 0;
151    while conv_idx < s.len() {
152        // Update value if not 0u8
153        str_idx = cur_row as usize * n_cols + cur_col as usize;
154        if arr[str_idx] != 0u8 {
155            output[conv_idx] = arr[str_idx];
156            conv_idx += 1;
157        }
158        // Change position.
159        if cur_row < n_rows - 1 {
160            cur_row += 1;
161        } else {
162            cur_row = 0;
163            cur_col += 1;
164        }
165    }
166    String::from_utf8(output.to_vec()).unwrap()
167}
168
169#[cfg(test)]
170#[test]
171fn test_conversion_s1() {
172    assert!(convert_s1(String::from("PAPAL"), 1) == String::from("PAPAL"));
173}
174
175/// Convert using string stacks
176///
177/// Considering the parameter constraints of input string length and
178/// row count, we can use stacks to do fast conversion.
179///
180/// # Arguments
181/// * `s` input string
182/// * `num_rows` number of rows to layout
183fn convert_s2(s: String, num_rows: i32) -> String {
184    let mut rows = vec![String::new(); num_rows as usize];
185
186    let mut cur_row: i32 = 0;
187    let mut go_down: bool = true;
188    for val in s.bytes() {
189        rows[cur_row as usize].push(val as char);
190        if !go_down && cur_row == 0 {
191            go_down = true;
192        } else if go_down && cur_row == num_rows - 1 {
193            go_down = false;
194        }
195
196        if go_down {
197            cur_row += 1;
198        } else {
199            cur_row -= 1;
200        }
201
202        cur_row = i32::min(num_rows - 1, cur_row);
203        cur_row = i32::max(0, cur_row);
204    }
205
206    rows.join("").to_string()
207}
208
209#[cfg(test)]
210#[test]
211fn test_conversion_s2() {
212    assert!(convert_s2(String::from("PAPAL"), 2) == String::from("PPLAA"));
213}