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/sorting-the-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
Cho một chuỗi câu (sentence) là một danh sách các từ được phân tách bằng một khoảng trắng, chuỗi câu này không có khoảng trắng ở đầu và cuối câu. Mỗi từ trong câu bao gồm các chữ cái tiếng Anh viết hoa và viết thường.
Hãy sắp xếp chuỗi câu này về đúng vị trí với mỗi từ được đánh số thứ tự ở cuối mỗi từ.
Ví dụ: câu "This is a sentence " có thể xáo trộn thành "sentence4 a3 is2 This1" hoặc là "is2 sentence4 This1 a3".
Cho bạn một chuỗi câu đã bị xáo trộn s không dài quá 9 từ, hãy sắp xếp lại và trả về chuỗi s hoành chỉnh.
Điều kiện bài toán:
2 <= s.length <= 200.sgồm các chữ cái tiếng Anh viết hoa và viết thường, khoảng trắng, chữ số từ1đến9.- Độ dài của
skhông quá 9 từ. - Mỗi từ trong
sđược phân tách bằng một khoảng trắng. skhông có khoảng trắng ở đầu và cuối.
Bài toán minh họa 1:
Input: s = "is2 sentence4 This1 a3"
Output: "This is a sentence"
Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.
Bài toán minh họa 2:
Input: s = "Myself2 Me1 I4 and3"
Output: "Me Myself and I"
Explanation: Sort the words in s to their original positions "Me1 Myself2 and3 I4", then remove the numbers.
3. Phân tích
Ồ kế, bài này cho chúng ta một chuỗi s là một câu đã bị xáo trộn, mỗi từ trong câu có số thứ tự ở cuối. Cũng không có gì quá phức tạp, chúng ta sẽ cần làm ba công việc chính sau:
Chúng ta sẽ tách chuỗi
sthành một mảng chuỗi chứa các từ củas, cùng với đó là một mảng chuỗi mớianssẽ chứa các từ củasnhưng sẽ được chúng ta sắp xếp đúng thứ tự.Tiếp theo chúng ta cần có một function làm nhiệm vụ lấy số thứ tự của mỗi từ trong chuỗi
s, để có thể xác định vị trí của các từ trong mảngans.Khi đã đặt mỗi từ vào đúng vị trí rồi, chúng ta sẽ xóa chữ số ở cuối mỗi từ đi, ghép từ ở mảng
ansthành một câu được phân tách với nhau bằng khoảng trắng.Thế là xong! Khá là đơn giản đấy nhể? Đến bước tiếp theo thôi.
4. Code chạy bằng cơm
Đầu tiên chúng ta sẽ tạo ra một mảng chứa các từ trong chuỗi s đã cho, cùng với đó là một mảng mới có kích thước tương tự:
Tiếp theo chúng ta cần một function làm nhiệm vụ lấy ra được số thứ tự ở cuối mỗi từ. Và để biến kí tự cuối đó chuyển đổi thành dạng số nguyên int thì ta sử dụng method Character.getNumericValue() để đổi dạng char thành int:
Đã biết được số thứ tự của từ rồi thì chúng ta cần làm thêm một việc nữa, ấy là xóa kí tự cuối chứa chữ số của từ đi. Ta sử dụng method substring() để làm điều này, kí tự cuối của một chuỗi word sẽ là word.length() - 1:
Bởi vì số thứ tự đằng sau mỗi từ bắt đầu từ 1, trong khi chỉ mục của mảng mặc định bắt đầu từ 0, vậy nên mỗi khi thêm một phần tử vào mảng ans, ta cần trừ chỉ mục của mỗi từ đi 1:
Cuối cùng, khi tất cả các từ đã vào đúng vị trí trong mảng ans, ta sẽ ghép chúng lại với nhau, phân tách bởi một khoảng trắng bằng method String.join():
Done!
5. Code thôi chờ gì nữa
Code của chúng ta sẽ như sau:
public static String sortSentence(String s) {
String[] arr = s.split(" ");
String[] ans = new String[arr.length];
for (String word : arr) {
int index = getIndex(word);
for (int i = 0; i < ans.length; i++) {
ans[index - 1] = removeLastChar(word);
}
}
String res = String.join(" ", ans);
return res;
}
// function làm nhiệm vụ lấy số thứ tự của mỗi từ
public static int getIndex(String word){
char lastChar = word.charAt(word.length() - 1);
int index = Character.getNumericValue(lastChar);
return index;
}
// function làm nhiệm vụ xóa số thứ tự ở cuối mỗi từ
public static String removeLastChar(String word){
return word.substring(0, word.length() - 1);
}
Chia nhỏ công việc ra sẽ giúp chúng ta dễ tư duy, cũng như dễ bảo trì, fix bug sau này nhé các bạn.
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