Reverse Words in a String

Q: Độ phức tạp thời gian của bài toán Đảo ngược các từ trong chuỗi là bao nhiêu?

Cả hai cách tiếp cận đều chạy trong thời gian O(n) với chuỗi có độ dài n , vì mỗi ký tự được đọc và ghi một số lần không đổi. Cách tách chuỗi cần thêm không gian O(n) cho danh sách các từ. Đảo ngược toàn bộ chuỗi rồi đảo ngược từng từ cần thêm không gian O(1) trên một mảng ký tự mà bạn có thể chỉnh sửa.

Trung bìnhMảng và chuỗi Hai con trỏ

+10

Bạn nhận được một chuỗi s gồm các từ và dấu cách. Một từ là một dãy chữ cái và chữ số không có dấu cách bên trong. Các từ có thể cách nhau bởi nhiều hơn một dấu cách, và s có thể bắt đầu hoặc kết thúc bằng dấu cách.

Trả về các từ theo thứ tự ngược lại, nối với nhau bằng đúng một dấu cách, không có dấu cách ở đầu hoặc cuối. Mỗi từ giữ nguyên cách viết, chỉ có thứ tự các từ thay đổi.

Hàm

reverseWords(s: string) → string

sstring: chữ cái, chữ số và dấu cách chứa ít nhất một từ
Trả vềstring: các từ của s theo thứ tự ngược lại, cách nhau bằng một dấu cách

Ràng buộc

1 ≤ s.length ≤ 10⁴
s chỉ chứa các chữ cái tiếng Anh, chữ số và dấu cách.
s chứa ít nhất một từ.

Ví dụ

Đầu vào: s = "Coddy runs in 15 languages"
Đầu ra: "languages 15 in runs Coddy"
Giải thích: Các từ là Coddy, runs, in, 15 và languages. Đọc từ cuối lên đầu, chúng tạo thành languages 15 in runs Coddy; 15 được tính là một từ vì từ có thể chứa chữ số.

Đầu vào: s = " practice makes progress "
Đầu ra: "progress makes practice"
Giải thích: Các khoảng trắng ở cả hai đầu bị loại bỏ, còn các chuỗi gồm hai và ba khoảng trắng giữa các từ được rút gọn thành một. Ba từ được xuất ra theo thứ tự từ cuối đến đầu: progress makes practice.

Đầu vào: s = " single "
Đầu ra: "single"
Giải thích: Một danh sách gồm một từ vẫn đọc giống nhau khi đọc ngược. Chỉ bỏ các khoảng trắng xung quanh, nên đáp án là single.

Câu hỏi mở rộng

Bạn có thể đảo ngược các từ nhưng giữ nguyên khoảng cách trong s: các dãy dấu cách giống nhau, có cùng độ dài và theo đúng thứ tự không?

Lời giải

Thứ tự các từ chỉ cần đảo ngược một lần; khoảng trắng là chỗ khiến lời giải dễ sai. Hãy xóa khoảng trắng ở hai đầu và khoảng trắng lặp lại giữa các từ, để giữa các từ trong câu trả lời chỉ còn đúng một khoảng trắng. Bạn có thể tách thành danh sách các từ, hoặc đảo ngược toàn bộ chuỗi rồi đảo ngược từng từ bên trong một mảng.

Chia thành các từ rồi nối chúng theo thứ tự ngược lại

Ý tưởng

Tách s thành các từ, đảo ngược danh sách rồi nối các từ bằng một dấu cách. Cần cẩn thận khi tách: tách " practice makes progress " tại từng dấu cách sẽ tạo ra sáu phần tử rỗng xung quanh ba từ. Loại bỏ các phần tử rỗng, ta được danh sách gồm practice, makes, progress.

Thao tác tách đọc từng ký tự một lần và thao tác nối ghi mỗi ký tự được giữ lại một lần, nên độ phức tạp thời gian là O(n) với chuỗi có độ dài n. Danh sách các từ và kết quả cần thêm O(n) bộ nhớ.

Thuật toán

Tách s theo khoảng trắng.
Loại bỏ các phần tử rỗng.
Đảo ngược danh sách từ.
Nối các từ bằng một dấu cách giữa mỗi từ rồi trả về kết quả.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Đảo ngược toàn bộ chuỗi, sau đó đảo ngược từng từ

Ý tưởng

Đảo ngược cả chuỗi sẽ đưa các từ về đúng thứ tự nhưng viết ngược từng từ: Coddy runs in 15 languages trở thành segaugnal 51 ni snur yddoC. Sau đó, đảo ngược từng từ riêng lẻ sẽ cho kết quả languages 15 in runs Coddy.

Các khoảng trắng cũng được xử lý trong cùng một lượt. Chỉ số read đi qua mảng đã đảo ngược và bỏ qua khoảng trắng; chỉ số write đánh dấu vị trí đặt ký tự tiếp theo được giữ lại. Việc sao chép không bao giờ ghi đè lên ký tự mà bạn vẫn cần, vì write không bao giờ vượt quá read: khoảng trắng được ghi trước một từ thay cho ít nhất một khoảng trắng mà read đã bỏ qua.

Mỗi ký tự được sao chép nhiều nhất một lần và đổi chỗ nhiều nhất hai lần, nên thời gian chạy là O(n), với O(1) bộ nhớ phụ trên bộ đệm ký tự mà bạn có thể chỉnh sửa. Ở đây, chuỗi được truyền vào dưới dạng giá trị, nên mỗi lời giải tạo một bản sao làm việc của s: tổng bộ nhớ là O(n).

Thuật toán

Sao chép s vào một mảng ký tự rồi đảo ngược toàn bộ mảng.
Duyệt mảng bằng chỉ số đọc và bỏ qua các khoảng trắng.
Ở mỗi từ, ghi một khoảng trắng trước trừ khi đó là từ đầu tiên, rồi sao chép các ký tự của từ vào chỉ số ghi.
Đảo ngược phần bạn vừa sao chép để từ đọc theo chiều xuôi.
Trả về write ký tự đầu tiên.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

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

Tách theo một dấu cách đơn và giữ lại mọi phần. "a b" được tách thành a, một phần rỗng và b, khi nối lại sẽ có hai dấu cách: "b a".
Tin rằng thao tác tách sẽ loại bỏ các phần ở hai đầu. split(" ") của Java loại bỏ các phần rỗng ở cuối nhưng giữ lại chúng ở đầu, vì vậy " a b" vẫn còn một phần rỗng.
Thêm dấu cách sau mỗi từ, kể cả từ cuối cùng, khiến kết quả có dấu cách ở cuối. Hãy đặt dấu cách trước mỗi từ, trừ từ đầu tiên.
Chỉ đảo một lần trong phiên bản sửa trực tiếp. Chỉ đảo thứ tự các từ sẽ cho kết quả yddoC snur ni 51 segaugnal.
Trong PHP và R, dữ liệu đầu vào chỉ gồm chữ số như 2026 có thể được nhận dưới dạng số. Hãy chuyển nó thành chuỗi trước khi tách.

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

Độ phức tạp thời gian của bài toán Đảo ngược các từ trong chuỗi là bao nhiêu?

Cả hai cách tiếp cận đều chạy trong thời gian O(n) với chuỗi có độ dài n, vì mỗi ký tự được đọc và ghi một số lần không đổi. Cách tách chuỗi cần thêm không gian O(n) cho danh sách các từ. Đảo ngược toàn bộ chuỗi rồi đảo ngược từng từ cần thêm không gian O(1) trên một mảng ký tự mà bạn có thể chỉnh sửa.

Làm thế nào để xử lý nhiều dấu cách giữa các từ?

Hãy xem một từ là một dãy ký tự không phải khoảng trắng và không bao giờ sao chép khoảng trắng từ đầu vào. Trong Python và Ruby, thao tác tách không có dấu phân cách, strings.Fields trong Go và split_whitespace trong Rust đều bỏ qua mọi dãy khoảng trắng cũng như khoảng trắng ở cả hai đầu; ở những nơi khác, hãy bỏ các phần tử rỗng. Sau đó, hãy đặt một dấu cách giữa các từ.

Bạn có thể đảo ngược các từ mà không dùng hàm split không?

Có. Quét từ cuối bên phải: bỏ qua khoảng trắng, đánh dấu nơi một từ kết thúc, di chuyển sang trái đến đầu từ đó rồi thêm từ vào, đặt một khoảng trắng trước từ trừ khi đó là từ đầu tiên. Mỗi ký tự chỉ được duyệt một lần, nên thời gian vẫn là O(n), và các từ xuất hiện theo thứ tự đảo ngược mà không cần danh sách để đảo.

def reverseWords(s):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "Coddy runs in 15 languages"

Đầu ra mong đợi

"languages 15 in runs Coddy"