2075. Decode the Slanted Ciphertext

MediumStringSimulation
Leetcode Link

Problem Description

This problem presents a string originalText that has been encoded using a "slanted transposition cipher" into a new string encodedText with the aid of a matrix with a defined number of rows rows. The encoding process consists of placing the characters of originalText into a matrix slantingly, from top to bottom and left to right in order of the text. The matrix is filled such that it would not have any empty columns on the right side after placing the entire originalText. Any remaining empty spaces in the matrix are filled with spaces ' '. encodedText is then obtained by reading the characters out of the matrix row by row and concatenating them.

For instance, if originalText = "cipher" and rows = 3, the process is visualized as placing "c", "i", "p" in the first row, shifting one position to the right for the second row to start with "h", and then "e" for the row after. Once the characters are placed, they are read off as "ch ie pr" to form encodedText. The goal is to reverse this process and recover originalText from encodedText and the given number of rows rows. Note that originalText doesn't contain any trailing spaces, and it is guaranteed there is only one originalText that corresponds to the input.

Intuition

To decode encodedText, we need to reverse-engineer the encoding process. We know the number of rows in which encodedText was originally laid out. By dividing the length of encodedText by the number of rows, we determine the number of columns that the plaintext was wrapped into. With this matrix's dimensions in mind, we can simulate the reading order the encoded text would have had if it were to be read slantingly.

The solution starts at each column of the top row and proceeds diagonally downward to the rightmost column, mimicking the slanted filling from the encoding process. We continue this diagonal reading for all starting positions in the top row.

To implement this in the solution, a simple loop iterates over each possible starting position (each column of the first row). For each start position, it reads off the characters diagonally until it either reaches the last row or the last column. These characters are appended to the ans list, which accumulates the original text. Finally, since encodedText could have trailing spaces (due to the padding of the matrix), but originalText doesn't, we use the .rstrip() function to remove any trailing whitespace from the reconstructed original text.

This process gives us the originalText without the need to actually build the matrix, which would be computationally more expensive and memory consuming.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Solution Approach

The implementation of the solution uses a simple yet efficient approach to decode encodedText. It avoids constructing the entire matrix and instead calculates the positions of the characters that would be in the original diagonal sequence based on their indices in the encoded string.

Here's how the algorithm unfolds:

  1. Determine the number of columns in the encoded matrix by dividing the length of encodedText by rows, the number of rows (cols = len(encodedText) // rows).

  2. Iterate over the range of columns to determine the starting point of each diagonal read process (for j in range(cols)).

  3. For each starting point, initialize variables x and y to keep track of the current row and column during the diagonal traversal. Initially x is set to 0 because we always start from the top, and y is set to the current column we are iterating over (x, y = 0, j).

  4. Start a while loop that continues as long as x is less than rows and y is less than cols. These conditions ensure we stay within the bounds of the conceptual matrix.

  5. Calculate the linear index of the current character in the encoded string (encodedText[x * cols + y]) and append it to the ans list. The multiplication x * cols skips entire rows to get to the current one, and y moves us along to the correct column.

  6. Increment both x and y to move diagonally down to the right in the matrix (x, y = x + 1, y + 1). This essentially simulates the row and column shift that occurs in a diagonal traversal.

  7. After completing the while loop for a diagonal line, the loop will iterate to the next starting column, and the process repeats until all columns have been used as starting points for the diagonal reads.

  8. Once all characters are read diagonally and stored in the ans list, combine them into a string (''.join(ans)) and strip any trailing spaces (rstrip()). This yields the original non-encoded text, which is then returned.

This solution effectively decodes the slanted cipher text without constructing the encoding matrix. It directly accesses the required characters by calculating their original and encoded positions through index arithmetic, which is both space and time-efficient. The choice of using a list to accumulate characters before joining them into a string is due to the fact that string concatenation can be costly in Python due to strings being immutable, while appending to a list and then joining is more efficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the problem content provided.

Suppose encodedText = "ch ie pr" and rows = 3. We want to decode this string to find the original text, supposedly originalText = "cipher".

  1. Calculate the number of columns: len("ch ie pr") // 3 = 8 // 3 = 2. So, we have 2 columns (ignoring the extra spaces).

  2. Iterate over the range of columns. Since we have 2 columns, the loop will run twice, for column indices 0 and 1.

  3. Loop iteration for column index 0:

    • Initialize x = 0, y = 0. This represents the first character of the top row.
    • While x < 3 and y < 2:
      • x = 0, y = 0, the current character is encodedText[0 * 2 + 0], which is "c".
      • Append "c" to the ans list.
      • Increment x and y to move diagonally, x = 1, y = 1.
    • Now x = 1, y = 1, the current character is encodedText[1 * 2 + 1], which is "i".
      • Append "i" to the ans list.
      • Increment x and y to move diagonally, x = 2, y = 2.
    • Since y is not less than cols, we have reached the end of the diagonal traversal for this starting point.

  4. Loop iteration for column index 1:

    • Initialize x = 0, y = 1. This represents the second column of the top row.
    • While x < 3 and y < 2:
      • x = 0, y = 1, the current character is encodedText[0 * 2 + 1], which is "h".
      • Append "h" to the ans list.
      • Increment x and y to move diagonally, x = 1, y = 2.
    • Since y is not less than cols, we move to the next row with x = 1 and reset y = 0.
    • Now x = 1, y = 0, the current character is encodedText[1 * 2 + 0], which is " ".
      • This is a space, but append it to the ans list anyway since we need to preserve the sequence.
      • Increment x and y to move diagonally, x = 2, y = 1.
    • Now x = 2, y = 1, the current character is encodedText[2 * 2 + 1], which is "p".
      • Append "p" to the ans list.
      • Increment x and y to move diagonally, x = 3, y = 2.
    • Since x is not less than rows, we have reached the end of the traversal for this starting point.

  5. The ans list now contains ["c", "i", "h", " ", "p"].

  6. Combine the characters into a string and strip trailing spaces: 'cih p'.rstrip() gives us "cihp".

  7. However, we notice that this is not the correct original text as the decode process puts the space in the wrong position. We should refine our solution by handling the spaces correctly.

So, let’s correct the steps to account for the shift that occurs at each row of the slanted transposition:

  • Increment x and y to move diagonally, if y reaches the number of columns, reset y to 0 and increase x: This mimics the wrapping to the next line in the slanted transposition.

Here's the corrected list of characters following the approach and the adjustment:

1  ch
2   i
3   e
4 pr
  • The diagonal traversal from column 0: "c", "i", "p" (top-to-bottom).
  • The diagonal traversal from column 1: "h", "e" (top-to-bottom).

So the correct ans list would contain ["c", "i", "p", "h", "e"]. We join them into a string without needing to strip spaces (since we handled the spaces correctly): ''.join(["c", "i", "p", "h", "e"]) gives us "cipher", which is our desired original text.

Solution Implementation

1class Solution:
2    def decode_ciphertext(self, encoded_text: str, rows: int) -> str:
3        # Initialize a list to hold the decoded characters
4        decoded_characters = []
5      
6        # Calculate the number of columns based on the length of the encoded text and number of rows
7        cols = len(encoded_text) // rows
8      
9        # Iterate over each column index starting from 0
10        for col_index in range(cols):
11            # Initialize starting point
12            row, col = 0, col_index
13          
14            # Traverse the encoded text by moving diagonally in the matrix
15            # constructed by rows and columns
16            while row < rows and col < cols:
17                # Determine the linear index for the current position in the (row, col) matrix
18                linear_index = row * cols + col
19              
20                # Append the corresponding character to the decoded list
21                decoded_characters.append(encoded_text[linear_index])
22              
23                # Move diagonally: go to next row and next column
24                row, col = row + 1, col + 1
25      
26        # Join the decoded characters to form the decoded string.
27        # Strip trailing spaces if any.
28        return ''.join(decoded_characters).rstrip()
29
1class Solution {
2
3    // Function to decode the cipher text given the number of rows
4    public String decodeCiphertext(String encodedText, int rows) {
5        // StringBuilder to build the decoded string
6        StringBuilder decodedText = new StringBuilder();
7      
8        // Calculate the number of columns based on the length of the encoded text and number of rows
9        int columns = encodedText.length() / rows;
10      
11        // Loop through the columns; start each diagonal from a new column
12        for (int colStart = 0; colStart < columns; ++colStart) {
13            // Initialize the row and column pointers for the start of the diagonal
14            for (int row = 0, col = colStart; row < rows && col < columns; ++row, ++col) {
15                // Calculate the index in the encodedText string and append the character at this index
16                decodedText.append(encodedText.charAt(row * columns + col));
17            }
18        }
19      
20        // Remove trailing spaces from the decoded string
21        while (decodedText.length() > 0 && decodedText.charAt(decodedText.length() - 1) == ' ') {
22            decodedText.deleteCharAt(decodedText.length() - 1);
23        }
24      
25        // Return the decoded string
26        return decodedText.toString();
27    }
28}
29
1#include <string>
2
3class Solution {
4public:
5    // Decodes the ciphertext from the encoded text given the number of rows of the encoded grid
6    std::string decodeCiphertext(std::string encodedText, int rows) {
7        // Initialize the decoded string
8        std::string decoded;
9        // Find out the number of columns based on the size of encoded text and number of rows
10        int cols = encodedText.size() / rows;
11      
12        // Iterate over each column of the grid
13        for (int col = 0; col < cols; ++col) {
14            // For every column, traverse diagonally starting from (0, col)
15            for (int row = 0, y = col; row < rows && y < cols; ++row, ++y) {
16                // Add character at (row, y) to the decoded string
17                decoded += encodedText[row * cols + y];
18            }
19        }
20      
21        // Trim any trailing spaces from the decoded string
22        while (!decoded.empty() && decoded.back() == ' ') {
23            decoded.pop_back();
24        }
25      
26        // Return the decoded string
27        return decoded;
28    }
29};
30
1function decodeCiphertext(encodedText: string, rows: number): string {
2    // Compute the number of columns based on the length of encoded text and the number of rows.
3    const columns = Math.ceil(encodedText.length / rows);
4    let decodedCharacters: string[] = [];
5
6    // Traverse the encoded text diagonally starting at each column.
7    for (let columnOffset = 0; columnOffset <= columns; columnOffset++) {
8        // Start from the first row and the current column offset, 
9        // moving diagonally through the text and adding the characters to the result.
10        for (let row = 0, col = columnOffset; row < rows && col < columns; row++, col++) {
11            decodedCharacters.push(encodedText.charAt(row * columns + col));
12        }
13    }
14
15    // Combine the characters to form the decoded string and trim any trailing spaces.
16    return decodedCharacters.join('').trimEnd();
17}
18
Not Sure What to Study? Take the 2-min Quiz：

Which technique can we use to find the middle of a linked list?

Time and Space Complexity

The time complexity of the code is O(rows * cols) since the main computation happens in a nested loop where x goes from 0 to rows - 1, and y goes from 0 to cols - 1. In each iteration of the loop, it performs a constant time operation of adding a single character to the ans list. Since rows * cols is also the length of the encodedText, the complexity could also be given as O(n) where n is the length of encodedText.

The space complexity is O(n) as well, due to the ans list which at most will contain n characters (where n is the length of encodedText). The .rstrip() function is called on a ''.join(ans) which is a string of the same length as ans, but since strings are immutable in Python, this operation generates a new string so it doesn't increase the space complexity beyond O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫