Permutation in String

Q: Độ phức tạp thời gian của Permutation in String là gì?

Với cửa sổ trượt, độ phức tạp là O(m + n) , trong đó m là độ dài của s1 và n là độ dài của s2 . Bạn đếm s1 một lần, sau đó mỗi chữ cái của s2 đi vào cửa sổ một lần và rời khỏi cửa sổ một lần. Đếm lại từ đầu cho từng cửa sổ sẽ tốn O(n · m) .

Q: Permutation in String có giống với việc tìm một từ đảo chữ trong chuỗi không?

Đúng vậy. Một hoán vị (permutation) của s1 là một từ đảo chữ (anagram) của nó, nên câu hỏi là liệu có chuỗi con nào trong s2 có độ dài m và là từ đảo chữ của s1 hay không. Cách kiểm tra hai chuỗi có phải là từ đảo chữ của nhau hay không sẽ so sánh số lần xuất hiện của từng ký tự một lần; ở đây, cách kiểm tra đó chạy trên một cửa sổ trượt.

Trung bìnhCửa sổ trượt Băm

+10

Hoán vị của một chuỗi gồm các chữ cái giống nhau theo thứ tự bất kỳ, mỗi chữ cái xuất hiện số lần bằng với chuỗi ban đầu: tar, rat và art là các hoán vị của nhau. Bạn có hai chuỗi s1 và s2 gồm các chữ cái tiếng Anh viết thường. Trả về true nếu một hoán vị nào đó của s1 xuất hiện trong s2 dưới dạng chuỗi con (một dãy ký tự liên tiếp), nếu không thì trả về false.

Hàm

checkInclusion(s1: string, s2: string) → boolean

s1string: các chữ cái cần sắp xếp lại
s2string: chuỗi cần tìm trong
Trả vềboolean: true nếu một chuỗi con của s2 là một hoán vị của s1

Ràng buộc

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 và s2 chỉ chứa các chữ cái tiếng Anh viết thường (a đến z).
s1 có thể dài hơn s2.

Ví dụ

Đầu vào: s1 = "tar"s2 = "smartphone"
Đầu ra: true
Giải thích: Chuỗi con art ở các chỉ số từ 2 đến 4 của smartphone có một a, một r và một t, cùng các ký tự với tar.

Đầu vào: s1 = "noon"s2 = "onion"
Đầu ra: false
Giải thích: Các cửa sổ có độ dài 4 là onio và nion. noon cần hai chữ n và hai chữ o, nhưng mỗi cửa sổ lại có một chữ i thay cho một trong số đó.

Đầu vào: s1 = "abcd"s2 = "dcb"
Đầu ra: false
Giải thích: Mọi hoán vị của abcd đều có 4 chữ cái, còn dcb chỉ có 3 chữ cái, nên không thể chứa một hoán vị như vậy.

Câu hỏi mở rộng

Bạn có thể trả về mọi chỉ số trong s2 nơi một hoán vị của s1 bắt đầu, vẫn trong thời gian O(m + n) không?

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

Liệt kê tất cả hoán vị là việc bất khả thi: 10 chữ cái đã có 3,628,800 cách sắp xếp. Thay vào đó, hãy bỏ qua thứ tự. Một chuỗi con của s2 là hoán vị của s1 khi và chỉ khi chuỗi đó có độ dài m và số lần xuất hiện của mỗi chữ cái đều bằng nhau. Vì vậy, hãy trượt một cửa sổ có độ dài m qua s2, mỗi bước cập nhật số lần xuất hiện bằng cách thêm một chữ cái và bỏ đi một chữ cái.

Đếm lại mọi cửa sổ từ đầu

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

Ý tưởng

Đếm số lần xuất hiện của các chữ cái trong s1 vào một bảng gồm 26 số. Sau đó, lấy từng chuỗi con có độ dài m của s2, đếm các chữ cái trong đó vào một bảng mới rồi so sánh. Trong smartphone, các cửa sổ là sma, mar, art và cứ tiếp tục như vậy, còn art khớp với tar.

Cách này kiểm tra mọi ứng viên nên cho kết quả chính xác. Nhưng các cửa sổ liền kề có chung m-1 chữ cái, vậy mà bạn vẫn đếm lại tất cả: với m = 2 × 10^4 và n = 5 × 10^4, có 30,001 cửa sổ gồm 20,000 chữ cái, tức khoảng 6 × 10^8 bước.

Thuật toán

Nếu s1 dài hơn s2, trả về false.
Đếm các chữ cái trong s1 vào một bảng need gồm 26 số 0.
Với mỗi chỉ số bắt đầu từ 0 đến n-m, đếm các chữ cái trong m ký tự tính từ vị trí bắt đầu đó vào một bảng mới.
Nếu bảng đó bằng need, trả về true.
Sau cửa sổ cuối cùng, trả về false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Trượt cửa sổ và so sánh số lượng 26

Ý tưởng

Các cửa sổ liền kề khác nhau ở hai chữ cái: chuyển từ mar sang art thì bỏ m và thêm t. Vì vậy, hãy giữ một bảng cho cửa sổ hiện tại và cập nhật bảng bằng một lần +1 và một lần -1 ở mỗi bước.

Mỗi bước cần hai lần cập nhật và so sánh 26 con số, bất kể m là bao nhiêu: khoảng 26 × 50,000 = 1.3 × 10^6 phép toán với đầu vào lớn nhất.

Thuật toán

Nếu s1 dài hơn s2, trả về false.
Đếm các ký tự trong s1 vào need và m ký tự đầu tiên của s2 vào window.
Nếu hai bảng bằng nhau, trả về true.
Với mỗi i từ m đến n-1: cộng 1 cho s2[i], trừ 1 cho s2[i-m] và trả về true nếu hai bảng bằng nhau.
Trả về false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Trượt cửa sổ và theo dõi các chữ cái chưa cân bằng

Ý tưởng

Mỗi bước chỉ thay đổi hai số đếm, nên so sánh cả 26 chữ cái sẽ lặp lại công việc. Duy trì balance[c], số lần xuất hiện của c trong s1 trừ đi số lần xuất hiện trong cửa sổ, và unbalanced, số chữ cái có balance khác 0. Cửa sổ là một hoán vị của s1 chính xác khi unbalanced bằng 0.

Một quy tắc giúp bộ đếm luôn chính xác: trước khi thay đổi balance, cộng 1 vào unbalanced nếu balance bằng 0; sau đó, trừ 1 nếu balance bằng 0. Khi balance chuyển từ 2 sang 1, cả hai thao tác đều không xảy ra, như vậy là đúng. Với tar trong smartphone, ban đầu unbalanced bằng 3. s và m làm giá trị này tăng lên 5, a đưa nó xuống 4, thêm r và bỏ s khiến nó còn 2, rồi thêm t và bỏ m đưa nó về 0 tại art.

Bạn có thể kiểm tra ngay từ chữ cái đầu tiên: khi cửa sổ ngắn hơn m, tổng các balance là một số dương, nên có ít nhất một balance khác 0.

Thuật toán

Nếu s1 dài hơn s2, trả về false.
Đếm các ký tự trong s1 vào balance và đặt unbalanced bằng số chữ cái có giá trị cân bằng khác 0.
Với mỗi chỉ số i của s2, trừ 1 khỏi giá trị cân bằng của s2[i], cộng 1 vào unbalanced nếu giá trị cân bằng đó là 0 và trừ 1 nếu giá trị đó trở thành 0.
Nếu i ≥ m, cộng 1 vào giá trị cân bằng của s2[i-m] và cập nhật tương tự.
Nếu unbalanced bằng 0, trả về true. Sau vòng lặp, trả về false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

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

Chỉ kiểm tra xem mọi chữ cái của s1 có nằm trong cửa sổ hay không. onio chứa mọi chữ cái của noon nhưng không phải là một hoán vị của nó.
Xóa nhầm chữ cái. Khi s2[i] đi vào, s2[i-m] rời khỏi cửa sổ; xóa s2[i-m+1] sẽ loại bỏ một chữ cái vẫn còn nằm trong cửa sổ.
Bỏ qua cửa sổ đầu tiên. Nếu chỉ so sánh sau khi trượt, bạn sẽ không bao giờ tìm thấy tar ở chỉ số 0 của tarp.
Không trả về false trước khi kiểm tra xem s1 có dài hơn s2 hay không. Trong Rust, n - m với độ dài không dấu sẽ bị tràn dưới, còn trong Swift, phạm vi 0...(n - m) sẽ gây lỗi.
So sánh các mảng bằng == trong trường hợp toán tử này so sánh tham chiếu, như trong JavaScript và Dart. Trong Java, hãy dùng Arrays.equals.

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

Độ phức tạp thời gian của Permutation in String là gì?

Với cửa sổ trượt, độ phức tạp là O(m + n), trong đó m là độ dài của s1 và n là độ dài của s2. Bạn đếm s1 một lần, sau đó mỗi chữ cái của s2 đi vào cửa sổ một lần và rời khỏi cửa sổ một lần. Đếm lại từ đầu cho từng cửa sổ sẽ tốn O(n · m).

Permutation in String có giống với việc tìm một từ đảo chữ trong chuỗi không?

Đúng vậy. Một hoán vị (permutation) của s1 là một từ đảo chữ (anagram) của nó, nên câu hỏi là liệu có chuỗi con nào trong s2 có độ dài m và là từ đảo chữ của s1 hay không. Cách kiểm tra hai chuỗi có phải là từ đảo chữ của nhau hay không sẽ so sánh số lần xuất hiện của từng ký tự một lần; ở đây, cách kiểm tra đó chạy trên một cửa sổ trượt.

Tôi có thể dùng từ điển thay cho mảng gồm 26 bộ đếm không?

Đúng vậy, và bạn cần một từ điển (map) nếu chuỗi có thể chứa bất kỳ ký tự nào. Nếu chỉ có chữ cái thường, mảng gồm 26 phần tử sẽ nhanh hơn. Với từ điển, hãy xóa khóa khi số lần xuất hiện giảm xuống 0 để các từ điển chứa cùng chữ cái được xem là bằng nhau, hoặc dùng biến đếm unbalanced, cách này cũng hoạt động tương tự với từ điển.

def checkInclusion(s1, s2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s1 = "tar"
s2 = "smartphone"

Đầu ra mong đợi

true

Permutation in String

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Đếm lại mọi cửa sổ từ đầu

Trượt cửa sổ và so sánh số lượng 26

Trượt cửa sổ và theo dõi các chữ cái chưa cân bằ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ự