LeetCode 题解工作台
解码斜向换位密码
字符串 originalText 使用 斜向换位密码 ，经由 行数固定 为 rows 的矩阵辅助，加密得到一个字符串 encodedText 。 originalText 先按从左上到右下的方式放置到矩阵中。 先填充蓝色单元格，接着是红色单元格，然后是黄色单元格，以此类推，直到到达 original…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · string·结合·模拟
答案摘要
我们先计算出矩阵的列数 $cols = \textit{len}(encodedText) / rows$，然后按照题目描述的规则，从左上角开始遍历矩阵，将字符添加到答案中。 最后返回答案，注意去掉末尾的空格。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·模拟 题型思路
题目描述
字符串 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 <= 106encodedText仅由小写英文字母和' '组成encodedText是对某个 不含 尾随空格的originalText的一个有效编码1 <= rows <= 1000- 生成的测试用例满足 仅存在一个 可能的
originalText
解题思路
方法一：模拟
我们先计算出矩阵的列数 ，然后按照题目描述的规则，从左上角开始遍历矩阵，将字符添加到答案中。
最后返回答案，注意去掉末尾的空格。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def decodeCiphertext(self, encodedText: str, rows: int) -> str:
ans = []
cols = len(encodedText) // rows
for j in range(cols):
x, y = 0, j
while x < rows and y < cols:
ans.append(encodedText[x * cols + y])
x, y = x + 1, y + 1
return ''.join(ans).rstrip()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate determine the number of columns for the matrix based on the given rows?
- question_mark
Does the candidate correctly simulate the diagonal filling of the matrix?
- question_mark
Can the candidate optimize the matrix manipulation process without unnecessary computations?
常见陷阱
外企场景- error
Not correctly calculating the number of columns when given the rows.
- error
Misunderstanding the matrix filling order and transposition logic.
- error
Not accounting for the spaces in the encodedText and their correct placement in the matrix.
进阶变体
外企场景- arrow_right_alt
Varying the number of rows in the matrix.
- arrow_right_alt
Changing the encodedText length while keeping rows constant.
- arrow_right_alt
Encoding a larger text and requiring the candidate to handle edge cases in matrix filling.