Cells in a Range on an Excel Sheet

Difficulty: Easy | Acceptance: 84.20% | Paid: No Topics: String

A cell (r, c) of an Excel sheet is represented as a string "<col><row>" where <col> denotes column number c as alphabet letters and <row> is the row number r.

You are given a string s in the format "<col1><row1>:<col2><row2>", where <col1> represents the column c1, <row1> represents the row r1, etc.

Return a list of all cells (x, y) such that r1 ≤ x ≤ r2 and c1 ≤ y ≤ c2. The cells should be represented as strings in the format mentioned above and be sorted in non-decreasing order first by column and then by row.

• Examples
• Constraints
• Iterative Construction
• ASCII Arithmetic

Examples

Example 1:

Input: s = "K1:L2"
Output: ["K1","K2","L1","L2"]
Explanation:
The above diagram shows the 3 x 3 grid. The cells in the range are highlighted.

Example 2:

Input: s = "A1:A1"
Output: ["A1"]

Constraints

s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s consists of uppercase English letters, a colon, and digits.

Iterative Construction

Intuition Since the input string format is fixed (length 5), we can directly extract the start and end characters for columns and rows. We then iterate through the column range and, for each column, iterate through the row range to construct the cell strings.

Steps

• Extract the start column (s[0]), start row (s[1]), end column (s[3]), and end row (s[4]).
• Initialize an empty list to store results.
• Loop from the start column to the end column (inclusive).
• Inside the column loop, loop from the start row to the end row (inclusive).
• Concatenate the current column character and row character, then add to the result list.
• Return the result list.

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

Complexity

• Time: O(n), where n is the number of cells in the range (at most 9 * 9 = 81).
• Space: O(n) to store the result list.
• Notes: This is the most direct approach given the fixed input format.

ASCII Arithmetic

Intuition This approach emphasizes the underlying ASCII values of the characters. By converting characters to their integer ASCII codes, we can perform arithmetic to iterate through the range, then convert back to characters for string construction.

Steps

• Parse the start and end indices for columns and rows from the string.
• Convert column characters to their ASCII integer values.
• Iterate using integer arithmetic from the start value to the end value.
• Convert the integer back to a character during string construction.
• Repeat the process for rows (which are already digits).

class Solution:
    def cellsInRange(self, s: str) -> list[str]:
        res = []
        col_start, row_start, _, col_end, row_end = s
        for col_code in range(ord(col_start), ord(col_end) + 1):
            col = chr(col_code)
            for row_code in range(ord(row_start), ord(row_end) + 1):
                res.append(col + chr(row_code))
        return res

Complexity

• Time: O(n), where n is the number of cells in the range.
• Space: O(n) to store the result list.
• Notes: Functionally similar to the iterative approach, but highlights character encoding.