Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/cells-in-a-range-on-an-excel-sheet

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Một ô (r, c) của trang tính excel được biểu diễn dưới dạng chuỗi "<col><row>" trong đó:

  • <col> biểu thị số cột c của ô. Nó được đại diện bởi các chữ cái trong bảng chữ cái.

    Ví dụ: Cột thứ nhất sẽ là 'A', cột thứ hai sẽ là 'B', cột thứ ba sẽ là 'C', và cứ thế đến 'Z'.

  • <row> là số hàng r của ô. Hàng thứ r của ô được biểu diễn bằng số nguyên r.

    Cho bạn một chuỗi s với định dạng "<col1><row1>:<col2><rol2>", trong đó <col1> đại diện cho cột c1, <row1> đại diện cho hàngr1, <col2> đại diện cho cột c2, và đại diện cho hàng r2, sao cho r1 <= r2 và c1 <= c2.

    Trả về danh sách các ô (x, y) sao cho r1 <= x <= r2 và c1 <= y <= c2. Các ô phải được biểu diễn dưới dạng chuỗi ở định dạng được đề cập ở trên và được sắp xếp theo thứ tự không giảm, tên cột trước rồi đến số thứ tự của hàng.

    Điều kiện bài toán:

  • s.length == 5.

  • 'A' <= s[0] <= s[3] <= 'Z'.

  • '1' <= s[1] <= s[4] <= '9'.

  • s bao gồm chữ cái tiếng Anh viết hoa, chữ số và dấu ':'.

    Bài toán minh họa 1:
    leetcode-2194-1

Input: s = "K1:L2"
Output: ["K1","K2","L1","L2"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrows denote the order in which the cells should be presented.

Bài toán minh họa 2:
leetcode-2194-1

Input: s = "A1:F1"
Output: ["A1","B1","C1","D1","E1","F1"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrow denotes the order in which the cells should be presented.

3. Phân tích

Ố kề! Các bạn chắc cũng từng làm việc với file excel rồi đúng không ạ? Mỗi khi ta trỏ vào một cell (ô) bất kì, tọa độ của ô đó sẽ có dạng <cột><hàng>, ví dụ: A1, Z29, v.v… Và khi bạn chọn một dải các cột và hàng, các bạn sẽ thấy dải đó được hiện thị theo dạng <cột-đầu-tiên><hàng-đầu-tiên>:<cột-cuối-cùng><hàng-cuối-cùng>, ví dụ: A1:C9, E3:O9, v.v… Đó cùng là chuỗi dữ liệu đầu vào, đề bài yêu cầu từ chuỗi đó, chúng ta phải liệt kê hết tất cả tọa độ của các ô có trong dải được chọn đó, ví dụ: A1:C3 sẽ có các ô A1, A2, A3, B1, B2, B3, C1, C2, C3. Công việc của ta là phải trả về danh sách dạng List<String> bao gồm tọa độ của tất cả các ô trong chuỗi s đã cho.
leetcode-2194-3

Ta sẽ phải làm hai công việc chính:

  • Xác định chữ cái biểu thị cho cột, chữ số biểu thị cho hàng trong chuỗi đã cho.

  • Ghép chữ cái và chữ số với nhau theo định dạng <cột><hàng>, đi từng hàng của cột trước rồi tới cột sau đến khi hết.
    leetcode-2194-4

    Thế là xong! Tới bước tiếp theo!

4. Chạy code bằng cơm

Đầu tiên, chuỗi đầu vào sẽ có chiều dài = 5, và trình bày theo mảng sẽ có dạng như sau:
leetcode-2194-5

Nhờ có điều kiện điện đề bài mà ta biết rằng số cột tối đa có thể là 26, số hàng tối đa sẽ là 9, nên ta có thể dùng hai vòng lặp lồng nhau để giải quyết bài toán này.
Với mỗi cột, ta cần chạy hết các hàng của cột đó:
leetcode-2194-6

Ghép kí tự cột với kí tự số của hàng đó với nhau:
leetcode-2194-7

Rồi sử dụng method add() để thêm vào list cần trả về:
leetcode-2194-8

Xong cột này thì ta đến cột tiếp theo và lặp lại đến hết số cột:
leetcode-2194-9

Thế là xong!

5. Code thôi chờ gì nữa

Như vậy code của chúng ta sẽ như sau:

public static List<String> cellsInRange(String s) {
  List<String> res = new ArrayList<>();
  char firstCol = s.charAt(0), 
      lastCol = s.charAt(3),
      firstRow = s.charAt(1), 
      lastRow = s.charAt(4);
      

  for (int i = firstCol; i <= lastCol; i++) {
      for (int j = firstRow; j <= lastRow; j++) {
          String str = (char) i + String.valueOf((char) j);
          res.add(sBuilder.toString());
      }
  }

  return res;
}

Bài toán đến đây là giải quyết xong, tuy nhiên có một vấn đề, ấy là runtime (thời gian chạy) của chương trình chưa được tối ưu. Trong khi chạy chương trình, có hai vấn đề chúng ta cần lưu ý, một là runtime, hai là bộ nhớ. Bộ nhớ thì chúng ta có thể cải thiện bằng cách mua thêm, tuy nhiên tốc độ xử lý, thời gian chạy của chương trình thì không thể mua thêm được, chỉ có thể cải thiện bằng những dòng code của chúng ta mà thôi. Như ở trên chúng ta có thể thấy, cứ mỗi vòng lặp chúng ta lại tạo mới chuỗi str kia, vì String trong java là Immutable (bất biến) nên ta không thể sửa, cũng như ghi đè lên chuỗi cũ, nó sẽ liên tục tạo ra chuỗi mới trong bộ nhớ Heap.

Nếu các bạn chưa biết về tính bất biến của String trong java có thể đọc thêm bài viết của mình tại đây.

Ok vậy thì chúng ta nên cải thiện như thế nào? Rất may trong java hiện nay có hai class có thể giải quyết vấn đề này, ấy là class StringBuilder và class StringBuffer. Chúng có các method tác động lên các String Object giống như String Class và có những method mà String Class không hề có (ví dụ như insert(), delete() và reverse()).

Sự khác nhau giữa class StringBuilder và class StringBuffer các bạn cứ hiểu nôm na là:

  • class StringBuilder sử dụng trong môi trường không đa luồng để tối ưu hơn.
  • class StringBuffer thì ngược lại, sử dụng trong môi trường đa luồng.

Các bạn có thể tham khảo thêm bài viết về StringBuilder và StringBuffer tại bài viết này.

Vậy để giải quyết bài toán này, ta sẽ sử dụng class StringBuilder:

public static List<String> cellsInRange(String s) {
   List<String> res = new ArrayList<>();
   char firstCol = s.charAt(0), 
       lastCol = s.charAt(3),
       firstRow = s.charAt(1), 
       lastRow = s.charAt(4);
       
 
   for (int i = firstCol; i <= lastCol; i++) {
       for (int j = firstRow; j <= lastRow; j++) {
           StringBuilder sBuilder = new StringBuilder();
           sBuilder.append((char) i);
           sBuilder.append((char) j);
           res.add(sBuilder.toString());
       }
   }
 
   return res;
}

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!