We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Decode the Slanted Ciphertext

Difficulty: Medium

Problem Description

Given an encoded string encodedText and a number of rows rows, return the original string originalText that was encoded using a slanted transposition cipher.

Key Insights

  • The original text is filled into a matrix in a zigzag manner, starting from the top-left to the bottom-right.
  • The filling order follows a diagonal pattern, and the remaining cells in the matrix are filled with spaces.
  • The encoded string is formed by reading the matrix row-wise.
  • The number of columns can be derived based on the length of the encodedText and the number of rows.

Space and Time Complexity

Time Complexity: O(n) where n is the length of encodedText, since we process each character once.

Space Complexity: O(n) for storing the intermediate matrix.

Solution

To decode the slanted ciphertext, we can follow these steps:

  1. Calculate the number of columns in the matrix using the formula: columns = (length of encodedText + rows - 1) // rows.
  2. Create a matrix with the determined number of rows and columns, initialized with spaces.
  3. Fill the matrix by iterating over the encodedText in the zigzag (diagonal) manner.
  4. Read the matrix row-wise to reconstruct the originalText.

We will use a list of lists (2D array) to represent the matrix and process the characters accordingly.

Code Solutions

def decode(encodedText: str, rows: int) -> str:
    if rows == 0:
        return ""
    
    n = len(encodedText)
    columns = (n + rows - 1) // rows
    matrix = [[' ' for _ in range(columns)] for _ in range(rows)]
    
    index = 0
    for diag in range(rows + columns - 1):
        for r in range(rows):
            c = diag - r
            if 0 <= c < columns and index < n:
                matrix[r][c] = encodedText[index]
                index += 1
    
    originalText = []
    for r in range(rows):
        for c in range(columns):
            if matrix[r][c] != ' ':
                originalText.append(matrix[r][c])
    
    return ''.join(originalText)
← Back to All Questions