2194-Excel 表中某个范围内的单元格

Excel 表中的一个单元格 (r, c) 会以字符串 "<col><row>" 的形式进行表示，其中：

• <col> 即单元格的列号 c 。用英文字母表中的 字母 标识。
  • 例如，第 1 列用 'A' 表示，第 2 列用 'B' 表示，第 3 列用 'C' 表示，以此类推。
• <row> 即单元格的行号 r 。第 r 行就用 整数 r 标识。

给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ，其中 <col1> 表示 c1 列，<row1>
表示 r1 行，<col2> 表示 c2 列，<row2> 表示 r2 行，并满足 r1 <= r2 且 c1 <= c2 。

找出所有满足 r1 <= x <= r2 且 c1 <= y <= c2 的单元格，并以列表形式返回。单元格应该按前面描述的格式用 字符串
表示，并以 非递减 顺序排列（先按列排，再按行排）。

示例 1：

**输入：** s = "K1:L2"
**输出：** ["K1","K2","L1","L2"]
**解释：**
上图显示了列表中应该出现的单元格。
红色箭头指示单元格的出现顺序。

示例 2：

**输入：** s = "A1:F1"
**输出：** ["A1","B1","C1","D1","E1","F1"]
**解释：**
上图显示了列表中应该出现的单元格。 
红色箭头指示单元格的出现顺序。

提示：

• s.length == 5
• 'A' <= s[0] <= s[3] <= 'Z'
• '1' <= s[1] <= s[4] <= '9'
• s 由大写英文字母、数字、和 ':' 组成

方法一：模拟

思路与算法

根据题意，我们需要遍历满足列号字典序在 [r_1, r_2] 闭区间内，且行号在 [c_1, c_2] 内的所有单元格。

我们可以模拟题目中的遍历方式先按列升序遍历，再按行升序遍历目标单元格。与此同时，我们用数组 res 维护所有目标单元格，在遍历到每个目标单元格时，我们将列号对应字符与行号对应字符组合在一起并添加进 res 中。最终，我们返回 res 作为答案。

代码

[sol1-C++]

class Solution {
public:
    vector<string> cellsInRange(string s) {
        vector<string> res;
        for (char row = s[0]; row <= s[3]; ++row) {
            for (char col = s[1]; col <= s[4]; ++col) {
                string cell(1, row);
                cell.push_back(col);
                res.push_back(cell);
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def cellsInRange(self, s: str) -> List[str]:
        res = []
        for row in range(ord(s[0]), ord(s[3]) + 1):
            for col in range(ord(s[1]), ord(s[4]) + 1):
                res.append(chr(row) + chr(col))
        return res

复杂度分析

• 时间复杂度：O(mn)，其中 m 为列的取值范围，即大写英文字母的个数；n 为行的取值范围，即数字的个数。即为模拟遍历单元格的时间复杂度。

• 空间复杂度：O(1)，输出数组不计入空间复杂度。