Skip to main content

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"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 <= 250
  • word consists of lowercase English letters.
  • ch is 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)

  1. đầ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
  2. Kiểm tra nếu index < 0 tức là chuỗi ch không xuất hiện trong word
  3. Tiếp theo tạo 1 biến là revertString để lưu lại dãy cần revert
  4. Tạo vòng for chạy từ index đến 0 và cộng ký tự vào chuỗi này
  5. Trả về chuỗi revertString cộng với dãy word cắt từ vị trí index trở đi đến cuối cùng