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/truncate-sentence/
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 câu là một danh sách các từ được phân tách bằng một khoảng trắng và không có khoảng trắng ở đầu hoặc cuối. Mỗi từ chỉ bao gồm các chữ cái tiếng Anh viết hoa và viết thường (không có dấu chấm câu).
Ví dụ:
"Hello World","HELLO"và"hello world hello world"đều là câu.Bạn được cho một câu
svà một số nguyênk. Hãy cắt bớtssao cho nó chỉ chứaktừ đầu tiên. Trả vềssau khi đã cắt bớt.Điều kiện:
1 <= s.length <= 500.knằm trong khoảng[1, số từ trong câu s].schỉ bao gồm các chữ cái viết thường và viết hoa trong tiếng Anh.Mỗi từ trong
sđược phân tách bằng khoảng trắng.Không có khoảng trắng nào ở đầu và cuối câu.
Ví dụ 1:
Input: s = "Hello how are you Contestant", k = 4
Output: "Hello how are you"
Explanation:
The words in s are ["Hello", "how" "are", "you", "Contestant"].
The first 4 words are ["Hello", "how", "are", "you"].
Hence, you should return "Hello how are you".
Ví dụ 2:
Input: s = "What is the solution to this problem", k = 4
Output: "What is the solution"
Explanation:
The words in s are ["What", "is" "the", "solution", "to", "this", "problem"].
The first 4 words are ["What", "is", "the", "solution"].
Hence, you should return "What is the solution".
Ví dụ 3:
Input: s = "chopper is not a tanuki", k = 5
Output: "chopper is not a tanuki"
3. Phân tích
Ấu kề, đề bài này cũng không quá phức tạp đâu các bạn. Chúng ta chỉ cần cắt câu s sao cho nó có số k từ đầu tiên là được. Nhìn vào ba ví dụ của đề bài cũng khá trực quan nên cũng không cần giải thích nhiều. Vấn đề ở đây là làm thế nào để chúng ta có thể cắt ra được?
Các bạn định nghĩ tới method subString() đúng không ạ? Rất tiếc là nó hơi không hợp lí, ta không thể cắt bắt đầu từ 0 tới k được, vì k ở đây là số từ cần cắt bớt chứ không phải số index kết thúc để cắt.
Vậy nên tôi đề nghị chúng ta dùng tới StringBuilder. Bằng cách tách cái câu s này thành một mảng các từ words, lấy được từ nào ta nối vào StringBuilder cùng với đó là khoảng trắng theo sau. Tuy nhiên nếu lấy đến số k từ thì chuỗi cuối cùng của chúng ta sẽ tòi ra một khoảng trắng ở cuối, thế này không đúng. Vậy nên ta sẽ chỉ lấy đến từ áp chót trong mảng words kia thôi. Sau đó ta sẽ nối thêm từ cuối cùng vào phía sau SringBuilder để chuỗi cuối cùng của chúng ta không có khoảng trắng ở cuối câu.
Vậy là xong, hãy cùng xem code chạy thế nào nhé!
4. Code chạy bằng cơm
Chúng ta cần một đối tượng StringBuilder tên sb và biến câu s thành một mảng words. Ta cần một vòng lặp với con trỏ i đẻ thực hiện việc nối từ vào sb, bên cạnh đó ta biết rằng k là số từ chúng ta cần lấy, nghĩa là con trỏ i của chúng ta chỉ cần chạy từ 0 tới k mà thôi. Nhưng như đã nói ở trên, chúng ta không muốn khoảng trắng xuất hiện vô duyên ở cuối câu sau khi cắt, nên chúng ta chỉ cần i chạy đến k - 1 là được:
Tại i = 0, ta được từ đầu tiên nối vào sb kèm theo đó là khoảng trắng:
Tại i = 1, ta được từ tiếp theo nối vào sb kèm theo đó là khoảng trắng:
Tại i = 2, ta được từ đầu tiên nối vào sb kèm theo đó là khoảng trắng. Khi này i đã chạy tới giới hạn dừng của nó, tức là k - 1, vậy nên ta dừng việc nối từ kèm khoảng trắng phía sau vào sb:
Sau khi đã dừng vòng lặp, ta chỉ việc chỉ định nối thêm từ cuối cùng vào sb với vị trí của nó là k - 1 trong mảng words là được:
Cuối cùng ta chỉ cần biến đổi sb thành chuỗi với method toString() là xong.
5. Code bằng máy
Code của chúng ta như sau:
public static String truncateSentence(String s, int k) {
String[] words = s.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < k - 1; i++) {
sb.append(words[i]).append(" ");
}
sb.append(words[k - 1]);
return sb.toString();
}
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!!!
Bình luận