2000. Reverse Perfix of Word
Đề bài :
Cho một chuỗi word bắt đầu từ vị trí số 0 và một ký tự là ch, đảo chuỗi word bắt đầu từ vị trí 0 và kết thúc khi bắt đầu gặp chuỗi ch
nếu chuỗi ch không tồn tại thì không làm gì cả
Ví dụ :
Nếu word = "abcdefd" và ch = "d",bạn sẽ phải reverse bắt đầu từ vị trí 0 và kết thúc tại vị trí 3 (d nằm ở index số 3) kết quả sẽ là "dcbaefd"
Example 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".
Example 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".
Example 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".
Constraints:
1 <= word.length <= 250wordconsists of lowercase English letters.chis a lowercase English letter.
Bài giải :
/**
* @param {string} word
* @param {character} ch
* @return {string}
*/
var reversePrefix = function (word, ch) {
const index = word.indexOf(ch);
if (index < 0) {
return word;
} else {
let revertString = "";
for (let i = index; i >= 0; i--) {
revertString += word[i];
}
return (revertString += word.slice(index + 1, word.length));
}
};
Giải thích code:
Thuật toán này có độ phức tạp là 0(n)
Độ phức tạp về không gian là O(n)
- đầu tiên chúng ta sử dụng hàm indexOf một method của string để tìm vị trí xuất hiện của chuỗi ch trong word
- Kiểm tra nếu index < 0 tức là chuỗi
chkhông xuất hiện trongword - Tiếp theo tạo 1 biến là
revertStringđể lưu lại dãy cần revert - Tạo vòng for chạy từ index đến 0 và cộng ký tự vào chuỗi này
- Trả về chuỗi
revertStringcộng với dãy word cắt từ vị trí index trở đi đến cuối cùng