2075. 解码斜向换位密码

题目描述

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

解法

方法一：模拟

思考

密文按行填入矩阵后再沿对角线读出。已知行数则可还原列数，按对角线模拟即可。\(n \le 10^6\)，每个字符访问一次。

从每一列顶出发向右下走，追加字符，最后去掉题面保证的尾随空格。

我们先计算出矩阵的列数 \(cols = \textit{len}(encodedText) / rows\)，然后按照题目描述的规则，从左上角开始遍历矩阵，将字符添加到答案中。

最后返回答案，注意去掉末尾的空格。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为字符串 \(encodedText\) 的长度。

Python3JavaC++GoTypeScript

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()

class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        StringBuilder ans = new StringBuilder();
        int cols = encodedText.length() / rows;
        for (int j = 0; j < cols; ++j) {
            for (int x = 0, y = j; x < rows && y < cols; ++x, ++y) {
                ans.append(encodedText.charAt(x * cols + y));
            }
        }
        while (ans.length() > 0 && ans.charAt(ans.length() - 1) == ' ') {
            ans.deleteCharAt(ans.length() - 1);
        }
        return ans.toString();
    }
}

class Solution {
public:
    string decodeCiphertext(string encodedText, int rows) {
        string ans;
        int cols = encodedText.size() / rows;
        for (int j = 0; j < cols; ++j) {
            for (int x = 0, y = j; x < rows && y < cols; ++x, ++y) {
                ans += encodedText[x * cols + y];
            }
        }
        while (ans.size() && ans.back() == ' ') {
            ans.pop_back();
        }
        return ans;
    }
};

func decodeCiphertext(encodedText string, rows int) string {
    ans := []byte{}
    cols := len(encodedText) / rows
    for j := 0; j < cols; j++ {
        for x, y := 0, j; x < rows && y < cols; x, y = x+1, y+1 {
            ans = append(ans, encodedText[x*cols+y])
        }
    }
    for len(ans) > 0 && ans[len(ans)-1] == ' ' {
        ans = ans[:len(ans)-1]
    }
    return string(ans)
}

function decodeCiphertext(encodedText: string, rows: number): string {
    const cols = Math.ceil(encodedText.length / rows);
    const ans: string[] = [];
    for (let k = 0; k <= cols; k++) {
        for (let i = 0, j = k; i < rows && j < cols; i++, j++) {
            ans.push(encodedText[i * cols + j]);
        }
    }
    return ans.join('').trimEnd();
}

2075. 解码斜向换位密码

题目描述

解法

方法一：模拟

评论