Decode the Slanted Ciphertext
Problem
A string originalText is encoded using a slanted transposition cipher to a string encodedText with the help of a matrix having a fixed number of rows rows.
originalText is placed first in a top-left to bottom-right manner.
The blue cells are filled first, followed by the red cells, then the yellow cells, and so on, until we reach the end of originalText. The arrow indicates the order in which the cells are filled. All empty cells are filled with ' '. The number of columns is chosen such that the rightmost column will not be empty after filling in originalText.
encodedText is then formed by appending all characters of the matrix in a row-wise fashion.
The characters in the blue cells are appended first to encodedText, then the red cells, and so on, and finally the yellow cells. The arrow indicates the order in which the cells are accessed.
For example, if originalText = "cipher" and rows = 3, then we encode it in the following manner:
The blue arrows depict how originalText is placed in the matrix, and the red arrows denote the order in which encodedText is formed. In the above example, encodedText = "ch ie pr".
Given the encoded string encodedText and number of rows rows, return the original string originalText.
Note: originalText does not have any trailing spaces ' '. The test cases are generated such that there is only one possible originalText.
Examples
Example 1
Input: encodedText = "ch ie pr", rows = 3
Output: "cipher"
Explanation: This is the same example described in the problem description.
Example 2
Input: encodedText = "iveo eed l te olc", rows = 4
Output: "i love leetcode"
Explanation: The figure above denotes the matrix that was used to encode originalText.
The blue arrows show how we can find originalText from encodedText.
Example 3
Input: encodedText = "coding", rows = 1
Output: "coding"
Explanation: Since there is only 1 row, both originalText and encodedText are the same.
Constraints
0 <= encodedText.length <= 10^6encodedTextconsists of lowercase English letters and' 'only.encodedTextis a valid encoding of someoriginalTextthat does not have trailing spaces.1 <= rows <= 1000- The testcases are generated such that there is only one possible
originalText.
Solution
Method 1 – Matrix Simulation and Diagonal Traversal
Intuition
The encoded text is formed by writing the original text diagonally in a matrix and then reading it row by row. To decode, we reconstruct the matrix row-wise and then read the diagonals to recover the original text.
Approach
- Compute the number of columns as
cols = len(encodedText) // rows. - Fill a matrix of size
rows x colswith the characters fromencodedTextrow by row. - Traverse the matrix diagonally: for each diagonal starting from the first column, collect characters from
(i, j)whereiis the row andj = i + dis the column. - Concatenate the collected characters.
- Remove any trailing spaces from the result.
Code
C++
class Solution {
public:
string decodeCiphertext(string s, int rows) {
int n = s.size();
if (rows == 1) return s;
int cols = n / rows;
string ans;
for (int d = 0; d < cols; ++d) {
for (int i = 0; i < rows; ++i) {
int j = d + i;
if (j < cols) {
char c = s[i * cols + j];
ans += c;
}
}
}
while (!ans.empty() && ans.back() == ' ') ans.pop_back();
return ans;
}
};
Go
func decodeCiphertext(s string, rows int) string {
n := len(s)
if rows == 1 {
return s
}
cols := n / rows
ans := make([]byte, 0, n)
for d := 0; d < cols; d++ {
for i := 0; i < rows; i++ {
j := d + i
if j < cols {
ans = append(ans, s[i*cols+j])
}
}
}
// Remove trailing spaces
for len(ans) > 0 && ans[len(ans)-1] == ' ' {
ans = ans[:len(ans)-1]
}
return string(ans)
}
Java
class Solution {
public String decodeCiphertext(String s, int rows) {
int n = s.length();
if (rows == 1) return s;
int cols = n / rows;
StringBuilder ans = new StringBuilder();
for (int d = 0; d < cols; d++) {
for (int i = 0; i < rows; i++) {
int j = d + i;
if (j < cols) {
ans.append(s.charAt(i * cols + j));
}
}
}
// Remove trailing spaces
int len = ans.length();
while (len > 0 && ans.charAt(len - 1) == ' ') {
ans.setLength(--len);
}
return ans.toString();
}
}
Kotlin
class Solution {
fun decodeCiphertext(s: String, rows: Int): String {
if (rows == 1) return s
val n = s.length
val cols = n / rows
val ans = StringBuilder()
for (d in 0 until cols) {
for (i in 0 until rows) {
val j = d + i
if (j < cols) {
ans.append(s[i * cols + j])
}
}
}
return ans.trimEnd().toString()
}
}
Python
class Solution:
def decodeCiphertext(self, s: str, rows: int) -> str:
if rows == 1:
return s
n: int = len(s)
cols: int = n // rows
ans: list[str] = []
for d in range(cols):
for i in range(rows):
j = d + i
if j < cols:
ans.append(s[i * cols + j])
return ''.join(ans).rstrip()
Rust
impl Solution {
pub fn decode_ciphertext(s: String, rows: i32) -> String {
if rows == 1 { return s; }
let n = s.len();
let cols = n / rows as usize;
let s = s.as_bytes();
let mut ans = Vec::with_capacity(n);
for d in 0..cols {
for i in 0..rows as usize {
let j = d + i;
if j < cols {
ans.push(s[i * cols + j]);
}
}
}
while ans.last() == Some(&b' ') {
ans.pop();
}
String::from_utf8(ans).unwrap()
}
}
TypeScript
class Solution {
decodeCiphertext(s: string, rows: number): string {
if (rows === 1) return s;
const n = s.length;
const cols = Math.floor(n / rows);
let ans = '';
for (let d = 0; d < cols; d++) {
for (let i = 0; i < rows; i++) {
const j = d + i;
if (j < cols) {
ans += s[i * cols + j];
}
}
}
return ans.replace(/\s+$/, '');
}
}
Complexity
- ⏰ Time complexity:
O(n), wherenis the length ofencodedText, since we visit each character once. - 🧺 Space complexity:
O(n), for storing the matrix and the answer string.