Medium

题目描述

一个字符串 originalText 使用倾斜转置密码编码为字符串 encodedText，编码时使用一个固定行数 rows 的矩阵。

originalText 首先按照从左上到右下的倾斜方式放置在矩阵中。

蓝色单元格首先被填充，然后是红色单元格，接着是黄色单元格，以此类推，直到我们到达 originalText 的末尾。箭头指示单元格被填充的顺序。所有空单元格都用空格 ' ' 填充。选择列数使得在填入 originalText 后，最右边的列不会为空。

然后 encodedText 通过按行顺序附加矩阵的所有字符形成。

蓝色单元格中的字符首先被附加到 encodedText，然后是红色单元格，以此类推，最后是黄色单元格。箭头指示访问单元格的顺序。

例如，如果 originalText = "cipher" 且 rows = 3，那么我们按以下方式编码：

蓝色箭头描述了 originalText 如何放置在矩阵中，红色箭头表示 encodedText 的形成顺序。在上面的例子中，encodedText = "ch ie pr"。

给定编码字符串 encodedText 和行数 rows，返回原始字符串 originalText。

注意： originalText 没有任何尾随空格 ' '。测试用例生成保证只有一个可能的 originalText。

示例 1：

输入：encodedText = "ch   ie   pr", rows = 3
输出："cipher"
解释：这与问题描述中的示例相同。

示例 2：

输入：encodedText = "iveo    eed   l te   olc", rows = 4
输出："i love leetcode"
解释：上图表示用于编码 originalText 的矩阵。蓝色箭头显示我们如何从 encodedText 找到 originalText。

示例 3：

输入：encodedText = "coding", rows = 1
输出："coding"
解释：由于只有 1 行，originalText 和 encodedText 是相同的。

约束条件：

  • 0 <= encodedText.length <= 10^6
  • encodedText 仅由小写英文字母和 ' ' 组成
  • encodedText 是某个没有尾随空格的 originalText 的有效编码
  • 1 <= rows <= 1000
  • 测试用例生成保证只有一个可能的 originalText

解题思路

这道题的核心是理解编码和解码的过程：

  1. 理解编码过程：原始文本按照倾斜的方式（从左上到右下的对角线）填入矩阵，然后按行读取形成编码文本。

  2. 计算矩阵维度：首先需要确定矩阵的列数。由于 encodedText 是按行读取的，所以 cols = encodedText.length / rows。

  3. 重构矩阵：将 encodedText 按行填入矩阵中。

  4. 倾斜解码：按照编码时的倾斜路径（对角线）来读取字符。对于每个起始列 j，我们沿着对角线方向读取字符，即从位置 (0, j) 开始，按照 (0, j) -> (1, j+1) -> (2, j+2) -> ... 的路径读取。

  5. 去除尾随空格：最后需要移除结果字符串末尾的空格。

算法步骤：

  • 计算列数：cols = len(encodedText) / rows
  • 重构二维矩阵
  • 从每个起始列开始，沿对角线读取字符
  • 拼接所有字符并去除末尾空格

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是 encodedText 的长度。

代码实现

class Solution {
public:
    string decodeCiphertext(string encodedText, int rows) {
        if (rows == 1) return encodedText;
        
        int n = encodedText.length();
        int cols = n / rows;
        
        string result;
        
        // 对于每个起始列
        for (int j = 0; j < cols; j++) {
            // 沿对角线读取
            for (int i = 0; i < rows && j + i < cols; i++) {
                int pos = i * cols + j + i;
                result += encodedText[pos];
            }
        }
        
        // 去除尾随空格
        while (!result.empty() && result.back() == ' ') {
            result.pop_back();
        }
        
        return result;
    }
};

class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str:
        if rows == 1:
            return encodedText
        
        n = len(encodedText)
        cols = n // rows
        
        result = []
        
        # 对于每个起始列
        for j in range(cols):
            # 沿对角线读取
            for i in range(rows):
                if j + i < cols:
                    pos = i * cols + j + i
                    result.append(encodedText[pos])
        
        # 去除尾随空格
        return ''.join(result).rstrip()

public class Solution {
    public string DecodeCiphertext(string encodedText, int rows) {
        if (rows == 1) return encodedText;
        
        int n = encodedText.Length;
        int cols = n / rows;
        
        StringBuilder result = new StringBuilder();
        
        // 对于每个起始列
        for (int j = 0; j < cols; j++) {
            // 沿对角线读取
            for (int i = 0; i < rows && j + i < cols; i++) {
                int pos = i * cols + j + i;
                result.Append(encodedText[pos]);
            }
        }
        
        // 去除尾随空格
        return result.ToString().TrimEnd();
    }
}

var decodeCiphertext = function(encodedText, rows) {
    if (rows === 1) return encodedText;
    
    const cols = encodedText.length / rows;
    const matrix = [];
    
    // Fill matrix row by row from encodedText
    for (let i = 0; i < rows; i++) {
        matrix[i] = encodedText.slice(i * cols, (i + 1) * cols).split('');
    }
    
    let result = '';
    
    // Read diagonally starting from each column in first row
    for (let startCol = 0; startCol < cols; startCol++) {
        let row = 0;
        let col = startCol;
        
        while (row < rows && col < cols) {
            result += matrix[row][col];
            row++;
            col++;
        }
    }
    
    // Remove trailing spaces
    return result.replace(/\s+$/, '');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(n)

其中 n 是 encodedText 的长度。我们需要遍历整个字符串一次来重构原始文本，空间复杂度主要用于存储结果字符串。

相关题目