解码斜向换位密码

难度: Medium

字符串 originalText 使用 斜向换位密码 ，经由 行数固定 为 rows 的矩阵辅助，加密得到一个字符串 encodedText 。

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 是相同的。

示例 4：

输入：encodedText = " b  ac", rows = 2
输出：" abc"
解释：originalText 不能含尾随空格，但它可能会有一个或者多个前置空格。

提示：

0 <= encodedText.length <= 10⁶
encodedText 仅由小写英文字母和 ' ' 组成
encodedText 是对某个不含尾随空格的 originalText 的一个有效编码
1 <= rows <= 1000
生成的测试用例满足 仅存在一个 可能的 originalText

Submission

运行时间: 104 ms

内存: 87.5 MB

class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str:
        ans = []
        n = len(encodedText)
        col = n // rows + 1
        for start in range(col - 1):
            ans.append(encodedText[start::col])
        return ''.join(ans).rstrip()

Explain

题解的核心思路是通过构建一个与输入编码文本对应的矩阵，然后模拟解码过程来还原原始文本。首先确定矩阵的列数，其基于输入字符串长度和行数计算得到。接着，通过一个循环按列遍历矩阵，利用 Python 的字符串切片功能收集各列对应的字符，并将其拼接。最终使用 rstrip() 方法移除字符串末尾的空格，因为原始文本不包含尾随空格。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str:
        ans = []  # 用于存储解码后的字符
        n = len(encodedText)  # 编码文本的长度
        col = n // rows + 1  # 计算列数
        for start in range(col - 1):  # 遍历每一列的起始字符
            ans.append(encodedText[start::col])  # 从每一列的起始位置开始，步进为列数，收集所有列的字符
        return ''.join(ans).rstrip()  # 拼接所有列的字符，并移除尾随空格

Explore

为了准确计算矩阵的列数，需要使用输入字符串的长度除以行数的商，即`col = n // rows`。在题解给出的代码中，列数计算公式实际上是`col = n // rows + 1`，这可能是一个错误，因为这会导致列数多出一列，除非最后一列全为必要字符。正确的做法应该是直接使用`col = n // rows`，这样可以确保不会创建多余的列，同时每一列都会被有效利用。如果`n`不是`rows`的整数倍，最后一列可能部分为空，但这符合原始文本的特性。

Python中的切片操作`encodedText[start::col]`表示从字符串`encodedText`中开始于索引`start`，每隔`col`个字符取一个字符。这种方式正好符合斜向换位矩阵的解码过程，因为每一列字符在字符串中的位置是等间隔的。通过这种方法，可以从编码后的文本中按矩阵的列顺序提取出每列的字符，然后将它们组合起来还原原始文本。

使用`rstrip()`方法是为了移除最终字符串末尾可能存在的多余空格，这些空格可能来源于初始化矩阵时填充的空白字符，或者是因为行数不完全匹配导致的。如果原始文本末尾没有空格，使用`rstrip()`不会对原始文本的内容产生影响，只会移除由于编码或填充过程中产生的额外空格。确保不删除原始文本中必要的空格，应该在处理逻辑中区分填充空格和原始空格。

如果原字符串`originalText`的长度不是行数`rows`的整数倍，按照题解中的处理方式，最后一列可能包含不足或者空白字符，但这不会影响解码过程的正确性。在构建矩阵时，会正确地将所有字符按顺序填充进矩阵的对应位置。在解码时，由于使用了`rstrip()`方法移除了末尾的空白，因此可以恢复原始文本的内容，不受行数整除关系的影响。