Partition Labels

Q: Độ phức tạp thời gian của Partition Labels là bao nhiêu?

O(n) : một lượt duyệt ghi lại vị trí cuối cùng của từng chữ cái, lượt thứ hai đặt các điểm cắt. Bảng vị trí cuối cùng có 26 phần tử với mọi độ dài chuỗi, nên không gian phụ là O(1) , không tính đầu ra.

Trung bìnhTham lam Băm

+10

Bạn nhận được một chuỗi s gồm các chữ cái viết thường. Hãy chia chuỗi thành nhiều phần liên tiếp nhất có thể sao cho mỗi chữ cái chỉ xuất hiện trong một phần: nếu một chữ cái xuất hiện trong một phần, tất cả các lần xuất hiện của nó đều nằm trong phần đó. Trả về độ dài các phần theo thứ tự từ trái sang phải.

Hàm

partitionLabels(s: string) → integer-array

sstring: chuỗi cần cắt, chỉ dùng chữ cái thường
Trả vềinteger-array: độ dài của từng phần, từ trái sang phải

Ràng buộc

1 ≤ s.length ≤ 5 × 10⁴
s chỉ chứa các chữ cái tiếng Anh viết thường.
Các phần giữ nguyên thứ tự và ghép lại tạo thành toàn bộ s, vì vậy tổng độ dài của chúng bằng s.length.

Ví dụ

Đầu vào: s = "abacdcefe"
Đầu ra: [3, 3, 3]
Giải thích: Các chữ a nằm ở vị trí 0 và 2, các chữ c ở vị trí 3 và 5, còn các chữ e ở vị trí 6 và 8. Vì vậy, các điểm cắt nằm sau aba và cdc, và không phần nào có thể bị cắt thêm.

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

Chỉ được cắt ở nơi không có chữ cái nào xuất hiện ở cả hai phía, và đáp án tốt nhất là cắt tại mọi vị trí như vậy. Quét lại chuỗi cho mỗi vị trí sẽ tốn thời gian bậc hai. Trước tiên, hãy ghi lại vị trí cuối cùng của mỗi chữ cái, rồi duyệt một lượt từ trái sang phải để tìm mọi vị trí cắt: một phần phải kéo dài đến bản sao cuối cùng của mỗi chữ cái bên trong nó.

Kiểm tra mọi khoảng trống

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Có thể cắt tại một trong n-1 khoảng trống nếu không có chữ cái nào xuất hiện ở cả hai phía. Cắt tại mọi vị trí hợp lệ sẽ tạo ra nhiều phần nhất: giữa hai vị trí cắt hợp lệ liền kề, mọi chữ cái đều có tất cả bản sao nằm bên trong, nên đoạn đó là một phần hợp lệ; không thể cắt ở vị trí nào khác mà vẫn có đáp án hợp lệ.

Vì vậy, hãy kiểm tra từng khoảng trống: tập hợp các chữ cái ở mỗi phía và cắt nếu hai tập hợp không có phần tử chung. Với abacdcefe, khoảng trống sau aba có a và b ở bên trái, còn bên phải có c, d, e và f, nên bạn cắt tại đó. Mỗi lần kiểm tra cần đọc toàn bộ chuỗi, tổng cộng khoảng n² lần đọc: 2.5 × 10^9 lần với n = 5 × 10^4.

Thuật toán

Đặt start = 0, nơi phần hiện tại bắt đầu.
Với mỗi khoảng cắt cut từ 1 đến n-1 (khoảng ngay trước s[cut]), đánh dấu các chữ cái trong s[0..cut-1] và các chữ cái trong s[cut..n-1].
Nếu không có chữ cái nào được đánh dấu ở cả hai phía, cộng cut-start vào đáp án và đặt start = cut.
Sau vòng lặp, cộng phần cuối cùng, n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Gộp span của từng ký tự

Ý tưởng

Xem mỗi chữ cái như một khoảng từ vị trí xuất hiện đầu tiên đến vị trí xuất hiện cuối cùng. Một phần chứa chữ cái phải bao trọn khoảng của chữ đó, vì vậy các khoảng chồng lấp sẽ nằm chung một phần, và phần chồng lấp lan rộng: nếu a chồng lấp b và b chồng lấp c, cả ba nằm trong cùng một phần. Gộp các khoảng chồng lấp; mỗi khối sau khi gộp là một phần.

Để gộp, cần sắp xếp các khoảng theo điểm bắt đầu, nhưng bạn có thể làm việc đó mà không cần sắp xếp: duyệt chuỗi và lấy khoảng của một chữ cái tại vị trí xuất hiện đầu tiên của chữ đó. Trong codingisfun, i có khoảng [3, 6] và n có khoảng [4, 10], còn g, s, f và u đều xuất hiện lần đầu trước vị trí 10, nên chúng gộp thành [3, 10]. Với tối đa 26 chữ cái, các bảng vị trí luôn có kích thước cố định.

Thuật toán

Trong một lượt duyệt qua s, ghi lại first và last, vị trí đầu tiên và cuối cùng của mỗi chữ cái.
Duyệt lại s. Khi vị trí i là vị trí đầu tiên của chữ cái đó, khoảng của chữ cái ấy [i, last] là khoảng tiếp theo theo thứ tự vị trí bắt đầu.
Nếu khoảng bắt đầu sau end của khối hiện tại, hãy kết thúc khối với độ dài end-start+1 và bắt đầu khối mới tại i.
Dù thế nào, hãy đặt end = max(end, last).
Kết thúc khối cuối cùng và trả về các độ dài.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Mở rộng từng phần đến chữ cái cuối cùng

Ý tưởng

Bạn không cần các vị trí đầu tiên. Đọc từ trái sang phải và giữ end, vị trí cuối cùng xa nhất của bất kỳ chữ cái nào trong phần hiện tại. Mỗi chữ cái bạn đọc sẽ kéo dài end đến vị trí xuất hiện cuối cùng của nó nếu vị trí đó xa hơn.

Khi i chạm đến end, mọi chữ cái trong phần đều xuất hiện lần cuối ở vị trí i hoặc trước đó, nên được phép ngắt sau i. Trước thời điểm đó, một số chữ cái bạn đã đọc vẫn còn xuất hiện ở bên phải, nên không được ngắt sớm hơn trong phần. Lượt duyệt sẽ ngắt đúng tại các vị trí được phép. Trong abacdcefe, chữ a đặt end thành 2 và phần kết thúc tại i = 2; chữ c đặt giá trị này thành 5 và phần tiếp theo kết thúc tại 5.

Thuật toán

Trong một lượt duyệt, lưu last[c], vị trí cuối cùng của mỗi chữ cái c, trong một mảng gồm 26 phần tử.
Đặt start = 0 và end = 0.
Với mỗi vị trí i, đặt end = max(end, last[s[i]]).
Nếu i == end, cộng end-start+1 vào đáp án rồi đặt start = i+1.
Trả về các độ dài.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

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

Cắt ở lần xuất hiện cuối cùng của chữ cái hiện tại thay vì tại end của phần. Trong abcba, chữ c ở chỉ số 2 là lần xuất hiện cuối cùng của chính nó, nhưng cắt ở đó sẽ tách các chữ a và b.
Sai lệch một đơn vị khi tính độ dài: một phần từ start đến end, tính cả hai đầu mút, có end-start+1 chữ cái.
Trả về vị trí cắt thay vì độ dài. Với abacdcefe, đáp án là [3, 3, 3], không phải [2, 5, 8].
Quên phần cuối cùng trong cách tính khoảng cách. Không có khoảng cách nào theo sau phần đó, vì vậy hãy cộng n-start sau vòng lặp.

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

Độ phức tạp thời gian của Partition Labels là bao nhiêu?

O(n): một lượt duyệt ghi lại vị trí cuối cùng của từng chữ cái, lượt thứ hai đặt các điểm cắt. Bảng vị trí cuối cùng có 26 phần tử với mọi độ dài chuỗi, nên không gian phụ là O(1), không tính đầu ra.

Partition Labels có phải là bài toán gộp các khoảng không?

Đúng vậy. Mỗi chữ cái bao phủ khoảng từ lần xuất hiện đầu tiên đến lần xuất hiện cuối cùng, rồi gộp các khoảng chồng lấp để tạo thành các phần. Lượt duyệt tham lam thực hiện việc gộp ngay trong lúc duyệt, với end làm mép phải của khối đã gộp tính đến thời điểm đó.

Các nhãn phân vùng có thể trả về bao nhiêu phần?

Từ 1 đến 26. Mỗi phần có ít nhất một chữ cái không xuất hiện ở phần nào khác, và chỉ có 26 chữ cái thường. Một chuỗi có mỗi chữ cái xuất hiện đúng một lần sẽ cho 26 phần, mỗi phần dài 1; một chuỗi bắt đầu và kết thúc bằng cùng một chữ cái sẽ có một phần.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "abacdcefe"

Đầu ra mong đợi

[3, 3, 3]

Partition Labels

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Kiểm tra mọi khoảng trống

Gộp span của từng ký tự

Mở rộng từng phần đến chữ cái cuối cùng

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

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

Bài tập tương tự