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/reverse-prefix-of-word/
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 word
và kí tự ch
, hãy đảo ngược đoạn chuỗi bắt đầu từ index 0 đến chỗ xuất hiện kí tự ch
(bao gồm cả kí tự ch
). Nếu trong chuỗi word
không xuất hiện kí tự ch
thì không thay đổi gì.
Trả về kết quả là chuỗi đã được thay đổi.
Điều kiện đề bài:
1 <= word.length <= 250
word
bao gồm các chữ cái tiếng Anh viết thường.ch
là chữ cái tiếng Anh viết thường.
Bài toán minh họa 1:
Input: word = "abcdefd", ch = "d"
Output: "dcbaefd"
Explanation: The first occurrence of "d" is at index 3.
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "dcbaefd".
Bài toán minh họa 2:
Input: word = "xyxzxe", ch = "z"
Output: "zxyxxe"
Explanation: The first and only occurrence of "z" is at index 3.
Reverse the part of word from 0 to 3 (inclusive), the resulting string is "zxyxxe".
Bài toán minh họa 3:
Input: word = "abcd", ch = "z"
Output: "abcd"
Explanation: "z" does not exist in word.
You should not do any reverse operation, the resulting string is "abcd".
3. Phân tích
Âu kê! Bài toán cũng không có gì quá phức tạp cả, chúng ta cần làm ba công việc chính đó là:
- Tìm được index của kí tự
ch
trong chuỗiword
. - Cắt đoạn chuỗi bắt đầu từ index 0 đến kí tự
ch
rồi đảo ngược nó. - Ghép chuỗi đã đảo ngược với đoạn còn lại của chuỗi.
Phân tích xong, đến bước tiếp theo thôi!
4. Code chạy bằng cơm
Bước đầu tiên chúng ta cần làm là tìm index của kí tự ch
, cái này đơn giản thôi, làm một cái vòng lặp tìm ra index là xong.
Tiếp theo chúng ta cắt đoạn chuỗi bắt đầu từ index 0 đến kí tự ch
Cắt rồi thì ta đảo ngược chuỗi rồi ghép nó với chuỗi còn lại
Thế là xong! Đúng không ạ?
5. Đến giờ code rồi
Như đã phân tích ở trên, ta sẽ cần một function làm nhiệm vụ tìm ra được index của kí tự ch
trong chuỗi word
. Đầu vào sẽ là một chuỗi và kí tự được cho:
public static int findIndex(String word, char ch){
char[] charWord = word.toCharArray();
for (int i = 0; i < charWord.length; i++) {
if (charWord[i] == ch) {
return i;
}
}
return -1;
}
Tiếp theo chúng ta sẽ làm một function khác có nhiệm vụ đảo ngược chuỗi đã được cắt:
public static String reverse(String word){
String newStr = "";
char ch;
for (int i = 0; i < word.length(); i++) {
ch = word.charAt(i);
newStr = ch + newStr;
}
return newStr;
}
Khi có hai function trên rồi thì ta hoàn thành nốt bài toán thôi:
public static String reversePrefix(String word, char ch) {
int index = findIndex(word, ch)
if (index < 0) {
return word;
}
String sub1 = word.substring(0, index + 1);
String sub2 = word.substring(index + 1);
String reverse = reverse(sub1);
return reverse + sub2;
}
public static int findIndex(String word, char ch){
char[] charWord = word.toCharArray();
for (int i = 0; i < charWord.length; i++) {
if (charWord[i] == ch) {
return i;
}
}
return -1;
}
public static String reverse(String word){
String newStr = "";
char ch;
for (int i = 0; i < word.length(); i++) {
ch = word.charAt(i);
newStr = ch + newStr;
}
return newStr;
}
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.
Bình luận