Reverse a String

Q: Độ phức tạp thời gian của việc đảo ngược một chuỗi là bao nhiêu?

Đảo ngược mất thời gian O(n) , vì mỗi ký tự phải chuyển đến vị trí mới và được xử lý đúng một lần. Tạo chuỗi mới tốn thêm O(n) bộ nhớ. Hoán đổi bằng hai con trỏ chỉ cần thêm O(1) bộ nhớ khi các ký tự đã nằm trong một mảng có thể thay đổi.

Q: Làm thế nào để đảo ngược một chuỗi mà không dùng hàm đảo ngược có sẵn?

Sao chép các ký tự vào một mảng, đặt một con trỏ ở mỗi đầu, đổi chỗ hai ký tự rồi di chuyển các con trỏ lại gần nhau cho đến khi chúng gặp nhau. Hoặc lặp từ chỉ số cuối cùng về chỉ số đầu tiên và thêm từng ký tự vào một bộ dựng chuỗi. Cả hai cách đều tạo ra chuỗi đảo ngược chỉ trong một lượt.

Q: Bạn có thể đảo ngược một chuỗi ngay tại chỗ không?

Chỉ khi các ký tự nằm trong vùng đệm có thể thay đổi, chẳng hạn như mảng char trong C, Java hoặc C#, danh sách trong Python, hay std::string trong C++. Chuỗi trong Java, Python và JavaScript không thể thay đổi, vì vậy bạn sao chép chúng vào một mảng, hoán đổi các ký tự trong đó rồi tạo một chuỗi mới.

Người mớiMảng và chuỗi Hai con trỏ

+10

Bạn nhận được một chuỗi s gồm các chữ cái tiếng Anh và chữ số. Hãy trả về một chuỗi mới có các ký tự theo thứ tự ngược lại, sao cho ký tự cuối cùng đứng đầu tiên và ký tự đầu tiên đứng cuối cùng. Giữ nguyên từng ký tự, kể cả chữ hoa hay chữ thường.

Hàm

reverseString(s: string) → string

sstring: chuỗi cần đảo ngược
Trả vềstring: các ký tự của s theo thứ tự ngược

Ràng buộc

1 ≤ s.length ≤ 10⁴
s chỉ chứa các chữ cái tiếng Anh (a đến z, A đến Z) và chữ số (0 đến 9).

Ví dụ

Đầu vào: s = "Coddy2026"
Đầu ra: "6202yddoC"
Giải thích: Đọc Coddy2026 từ ký tự cuối cùng đến ký tự đầu tiên: 6, 2, 0, 2, rồi đến y, d, d, o và cuối cùng là chữ C viết hoa.

Đầu vào: s = "noon"
Đầu ra: "noon"
Giải thích: noon là một từ đối xứng, nên từ đảo ngược của nó vẫn là từ đó. Hai chữ n ở ngoài đổi chỗ cho nhau, rồi đến hai chữ o.

Câu hỏi mở rộng

Làm thế nào bạn đảo ngược thứ tự các từ trong một câu, biến hello big world thành world big hello, trong khi vẫn giữ nguyên thứ tự các chữ cái trong mỗi từ?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi ký tự có một vị trí đích cố định: ký tự ở chỉ số i thuộc về chỉ số n-1-i. Bạn có thể ghi các ký tự vào một chuỗi mới theo thứ tự đó hoặc đổi chỗ chúng theo từng cặp từ hai đầu. Phỏng vấn viên thường yêu cầu cách đổi chỗ, vì cùng thao tác dùng hai con trỏ này có thể đảo ngược mảng ngay tại chỗ và kiểm tra xem chuỗi có đối xứng hay không.

Sao chép các ký tự từ phía sau

Ý tưởng

Đảo ngược bắt đầu từ ký tự cuối cùng và kết thúc ở ký tự đầu tiên, vì vậy hãy lặp chỉ số từ n-1 giảm dần đến 0 và nối từng ký tự vào kết quả. Mỗi ký tự được đọc một lần và ghi một lần: độ phức tạp thời gian O(n), cộng thêm chuỗi kết quả có độ dài O(n).

Nối vào danh sách hoặc bộ dựng chuỗi rồi ghép một lần ở cuối. Thêm một ký tự vào chuỗi bất biến bằng + sẽ sao chép toàn bộ chuỗi mỗi lần, khoảng 5 × 10^7 lượt sao chép ký tự khi n = 10^4.

Thuật toán

Tạo một danh sách rỗng hoặc một bộ dựng chuỗi để chứa câu trả lời.
Lặp qua i từ n-1 xuống 0.
Thêm s[i] vào câu trả lời.
Nối các phần tử trong câu trả lời thành một chuỗi rồi trả về chuỗi đó.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Đổi từ cả hai đầu bằng hai con trỏ

Ý tưởng

Ký tự đầu tiên và cuối cùng đổi chỗ cho nhau, rồi đến ký tự thứ hai và ký tự áp chót, cứ thế tiến dần vào giữa. Đặt left tại chỉ số 0 và right tại n-1, đổi chỗ rồi dịch cả hai vào trong cho đến khi chúng gặp nhau hoặc vượt qua nhau. Mỗi lần đổi chỗ đưa hai ký tự về đúng vị trí cuối cùng, vì vậy cần n / 2 lần đổi chỗ để hoàn tất. Với độ dài lẻ, chẳng hạn xYz, ký tự ở giữa đã ở đúng vị trí và không bao giờ bị chạm đến.

Các lần đổi chỗ cần một biến tạm. Hầu hết ngôn ngữ không thể thay đổi chuỗi ngay tại chỗ, nên trước tiên bạn sao chép chuỗi vào một mảng ký tự, việc này tốn O(n). Khi đầu vào đã là một mảng có thể thay đổi, thao tác đảo ngược chỉ dùng thêm O(1) không gian.

Thuật toán

Sao chép s vào một mảng ký tự.
Đặt left = 0 và right = n-1.
Trong khi left < right, đổi chỗ các ký tự tại left và right, sau đó cộng 1 vào left và trừ 1 khỏi right.
Chuyển mảng trở lại thành chuỗi rồi trả về chuỗi đó.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Lỗi thường gặp và trường hợp biên

Lặp left đến tận n-1. Sau điểm giữa, mỗi cặp lại bị hoán đổi về vị trí ban đầu, khiến chuỗi không thay đổi. Dừng tại left < right.
Bắt đầu vòng lặp ngược tại n thay vì n-1, khiến chương trình đọc quá một vị trí sau phần cuối. Trong Lua và R, chỉ số chạy từ 1 đến n.
Quên ký tự kết thúc '\0' trong C. Bộ đệm có n byte là thiếu một byte, hãy cấp phát n + 1.
Hoán đổi mà không dùng biến tạm. Sau chars[left] = chars[right], ký tự cũ ở vị trí left sẽ mất, trừ khi ngôn ngữ của bạn hoán đổi đồng thời cả hai giá trị.

Câu hỏi thường gặp3

Độ phức tạp thời gian của việc đảo ngược một chuỗi là bao nhiêu?

Đảo ngược mất thời gian O(n), vì mỗi ký tự phải chuyển đến vị trí mới và được xử lý đúng một lần. Tạo chuỗi mới tốn thêm O(n) bộ nhớ. Hoán đổi bằng hai con trỏ chỉ cần thêm O(1) bộ nhớ khi các ký tự đã nằm trong một mảng có thể thay đổi.

Làm thế nào để đảo ngược một chuỗi mà không dùng hàm đảo ngược có sẵn?

Sao chép các ký tự vào một mảng, đặt một con trỏ ở mỗi đầu, đổi chỗ hai ký tự rồi di chuyển các con trỏ lại gần nhau cho đến khi chúng gặp nhau. Hoặc lặp từ chỉ số cuối cùng về chỉ số đầu tiên và thêm từng ký tự vào một bộ dựng chuỗi. Cả hai cách đều tạo ra chuỗi đảo ngược chỉ trong một lượt.

Bạn có thể đảo ngược một chuỗi ngay tại chỗ không?

Chỉ khi các ký tự nằm trong vùng đệm có thể thay đổi, chẳng hạn như mảng char trong C, Java hoặc C#, danh sách trong Python, hay std::string trong C++. Chuỗi trong Java, Python và JavaScript không thể thay đổi, vì vậy bạn sao chép chúng vào một mảng, hoán đổi các ký tự trong đó rồi tạo một chuỗi mới.

def reverseString(s):
    # Viết code ở đây
    return s

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "Coddy2026"

Đầu ra mong đợi

"6202yddoC"