2075-解码斜向换位密码

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

字符串 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

方法一：模拟

思路与算法

我们可以通过模拟原字符串放置到矩阵的流程来从加密字符串中得到原字符串。

对于给定的编码后字符串 encodedText 和辅助矩阵的行数 rows，辅助矩阵的列数满足 cols} = \textit{len}(\textit{encodedText}) / \textit{rows，其中 lens}(\dots) 为字符串的长度。

为了模拟编码过程，我们需要从左至右枚举每一条左上到右下的路径，并按顺序记录所有经过的字符。我们用坐标 (r, c) 来记录当前位置的行数与列数，该坐标在加密字符串中对应的字符即为 encodedText}[r \times \textit{cols} + c]。在遍历第 i\ (0 \le i < \textit{cols}) 条路径时，坐标初始值为 (0, i)；当记录完成坐标 (r, c) 对应字符后，我们需要判断当前坐标右下的坐标 (r + 1, c + 1) 是否合法（即是否辅助矩阵内）：如果坐标合法，则我们继续记录该坐标的字符；反之则从头开始遍历下一条路径。

当遍历完成所有路径后，我们将得到的字符串删去末尾的空格，即为编码前的原字符串。我们将该字符串返回作为答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string decodeCiphertext(string encodedText, int rows) {
        int cols = encodedText.size() / rows;   // 辅助矩阵的列数
        string res;   // 遍历到的字符
        for (int i = 0; i < cols; ++i){
            // 从左至右枚举每一条路径
            int r = 0;
            int c = i;
            while (r < rows && c < cols){
                res.push_back(encodedText[r*cols+c]);
                ++r;
                ++c;
            }
        }
        // 删去末尾空格
        while (res.size() and res.back() == ' '){
            res.pop_back();
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str:
        cols = len(encodedText) // rows   # 辅助矩阵的列数
        res = []   # 遍历到的字符
        for i in range(cols):
            # 从左至右枚举每一条路径
            r = 0
            c = i
            while r < rows and c < cols:
                res.append(encodedText[r*cols+c])
                r += 1
                c += 1
        # 删去末尾空格
        while res and res[-1] == ' ':
            res.pop()
        return "".join(res)

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 encodedText 的长度。即为遍历加密字符串生成解密字符串的时间复杂度。

  • 空间复杂度：由于不同语言的字符串实现与方法不同，空间复杂度也有所不同。对于 C++ 解法，空间复杂度为 O(1)；而对于 Python 解法，空间复杂度为 O(n)。

 Comments
On this page
2075-解码斜向换位密码