原文链接: https://leetcode-cn.com/problems/decode-the-slanted-ciphertext

英文原文

A string originalText is encoded using a slanted transposition cipher to a string encodedText with the help of a matrix having a fixed number of rows rows.

originalText is placed first in a top-left to bottom-right manner.

The blue cells are filled first, followed by the red cells, then the yellow cells, and so on, until we reach the end of originalText. The arrow indicates the order in which the cells are filled. All empty cells are filled with ' '. The number of columns is chosen such that the rightmost column will not be empty after filling in originalText.

encodedText is then formed by appending all characters of the matrix in a row-wise fashion.

The characters in the blue cells are appended first to encodedText, then the red cells, and so on, and finally the yellow cells. The arrow indicates the order in which the cells are accessed.

For example, if originalText = "cipher" and rows = 3, then we encode it in the following manner:

The blue arrows depict how originalText is placed in the matrix, and the red arrows denote the order in which encodedText is formed. In the above example, encodedText = "ch ie pr".

Given the encoded string encodedText and number of rows rows, return the original string originalText.

Note: originalText does not have any trailing spaces ' '. The test cases are generated such that there is only one possible originalText.

 

Example 1:

Input: encodedText = "ch   ie   pr", rows = 3
Output: "cipher"
Explanation: This is the same example described in the problem description.

Example 2:

Input: encodedText = "iveo    eed   l te   olc", rows = 4
Output: "i love leetcode"
Explanation: The figure above denotes the matrix that was used to encode originalText. 
The blue arrows show how we can find originalText from encodedText.

Example 3:

Input: encodedText = "coding", rows = 1
Output: "coding"
Explanation: Since there is only 1 row, both originalText and encodedText are the same.

Example 4:

Input: encodedText = " b  ac", rows = 2
Output: " abc"
Explanation: originalText cannot have trailing spaces, but it may be preceded by one or more spaces.

 

Constraints:

• 0 <= encodedText.length <= 106
• encodedText consists of lowercase English letters and ' ' only.
• encodedText is a valid encoding of some originalText that does not have trailing spaces.
• 1 <= rows <= 1000
• The testcases are generated such that there is only one possible originalText.

中文题目

字符串 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 <= 106
• encodedText 仅由小写英文字母和 ' ' 组成
• encodedText 是对某个 不含 尾随空格的 originalText 的一个有效编码
• 1 <= rows <= 1000
• 生成的测试用例满足 仅存在一个 可能的 originalText

通过代码

高赞题解

题目描述很长，实际上就是传入了一个二维矩阵，让你斜着扫描，返回去掉末尾空格的扫描结果。

由于 $\textit{encodedText}$ 是二维矩阵每行拼起来组成的一维字符串，因此二维矩阵的列数 $\textit{cols}=\dfrac{\textit{encodedText}.\textit{length}}{\textit{rows}}$，二维矩阵上的位置 $(i,j)$ 对应的就是 $\textit{encodedText}[i\cdot\textit{cols}+j]$。

func decodeCiphertext(encodedText string, rows int) string {
	ans := []byte{}
	for i, j, k, cols := 0, 0, 0, len(encodedText)/rows; k < cols; {
		ans = append(ans, encodedText[i*cols+j]) // 转换成在 encodedText 上的下标
		i++
		j++
		if i == rows || j == cols { // 触及边界
			k++
			i, j = 0, k // 移至下一条斜向
		}
	}
	return string(bytes.TrimRight(ans, " ")) // 移除末尾多余空格
}

统计信息

通过次数	提交次数	AC比率
3180	6977	45.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言