Regular Expression Matching

Q: Độ phức tạp thời gian của việc so khớp biểu thức chính quy là gì?

Lời giải dùng bảng chạy trong thời gian O(n × m) với chuỗi có độ dài n và mẫu có độ dài m , vì mỗi ô chỉ đọc tối đa hai ô khác. Lời giải cần O(n × m) bộ nhớ cho toàn bộ bảng, hoặc O(m) nếu dùng hai hàng. Đệ quy thông thường có thể mất thời gian theo hàm mũ với những mẫu có nhiều dấu sao.

KhóQuy hoạch động Đệ quy

+10

Bạn nhận được một chuỗi s và một mẫu p. Trong mẫu, một chữ cái khớp với chính chữ cái đó, dấu chấm . khớp với bất kỳ một chữ cái nào, và dấu sao * có nghĩa là có không hoặc nhiều bản sao của phần tử ngay trước nó, có thể là chữ cái hoặc dấu chấm. Trả về true nếu mẫu khớp với toàn bộ s, nếu không thì trả về false.

Hàm

isMatch(s: string, p: string) → boolean

sstring: chuỗi cần khớp, chỉ gồm chữ cái viết thường
pstring: mẫu gồm các chữ cái, dấu chấm và dấu sao
Trả vềboolean: đúng nếu p khớp với toàn bộ s, nếu không thì sai

Ràng buộc

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s chỉ chứa các chữ cái tiếng Anh viết thường.
p chỉ chứa các chữ cái tiếng Anh viết thường, . và *.
Mỗi * đứng sau một chữ cái hoặc ., vì vậy p không bao giờ bắt đầu bằng * và không bao giờ có hai dấu sao liên tiếp.

Ví dụ

Đầu vào: s = "moon"p = "mo*n"
Đầu ra: true
Giải thích: o* khớp với cả hai chữ o, nên m, o* và n ghép lại thành moon chính xác.

Đầu vào: s = "tree"p = "t.e"
Đầu ra: false
Giải thích: t.e khớp với tre, phần đầu của tree, nhưng chữ e cuối cùng còn thừa, trong khi một kết quả khớp phải bao phủ toàn bộ s.

Đầu vào: s = "sky"p = "z*s.*y"
Đầu ra: true
Giải thích: z* khớp với 0 lần xuất hiện của z, s khớp với s, .* khớp với k, và y khớp với y.

Câu hỏi mở rộng

Bạn cũng có thể hỗ trợ +, nghĩa là một hoặc nhiều bản sao của phần tử đứng trước nó, với cùng bảng 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

Dấu sao có thể nhận bất kỳ số lượng bản sao nào, và số lượng phù hợp phụ thuộc vào phần theo sau nó. Hãy xem một chữ cái cùng dấu sao của nó là một đơn vị có hai lựa chọn: bỏ qua, hoặc ăn một chữ cái rồi tiếp tục xét chữ cái đó. Một bảng ghi lại tiền tố (prefix) nào của s khớp với tiền tố nào của p sẽ thử từng lựa chọn một lần.

Ghép từ trái bằng đệ quy

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

Ý tưởng

So sánh các hậu tố: match(i, j) cho biết liệu s[i:] có khớp với p[j:] hay không. Chữ cái hoặc dấu chấm không có dấu sao phải khớp với s[i], phần còn lại cũng phải khớp. Một đơn vị x* hoặc lấy 0 bản sao rồi bỏ qua, hoặc lấy s[i] rồi tiếp tục ở cùng đơn vị, nhờ đó một dấu sao có thể lấy bất kỳ số lượng chữ cái nào. Hai nhánh này bao quát mọi lựa chọn mà dấu sao có thể thực hiện, nên không bỏ sót kết quả khớp nào.

Mỗi dấu sao chia quá trình tìm kiếm thành hai nhánh. Với 30 chữ cái a, mười bản sao của a* rồi đến một chữ b, đệ quy thử khoảng 8.5 × 10^8 cách phân chia các chữ cái cho những dấu sao trước khi trả lời false, trong khi chỉ có (n+1) × (m+1) cặp (i, j) khác nhau.

Thuật toán

Viết match(i, j) cho các hậu tố bắt đầu tại i và j.
Nếu j vượt quá cuối p, hãy trả về kết quả cho biết i có vượt quá cuối s hay không.
Đặt first bằng kết quả cho biết s[i] có tồn tại và p[j] là s[i] hoặc dấu chấm hay không.
Nếu p[j+1] là dấu sao, hãy trả về match(i, j+2) hoặc first and match(i+1, j).
Nếu không, hãy trả về first and match(i+1, j+1). Đáp án là match(0, 0).

def isMatch(s, p):
    n, m = len(s), len(p)

    def match(i, j):
        # Does s[i:] match p[j:]?
        if j == m:
            return i == n
        first = i < n and p[j] in (s[i], ".")
        if j + 1 < m and p[j + 1] == "*":
            # use p[j] zero times, or let it eat s[i] and stay on the same x*
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)

    return match(0, 0)

Điền vào bảng tiền tố

Ý tưởng

Gọi dp[i][j] cho biết i chữ cái đầu tiên của s có khớp với j ký tự đầu tiên của p hay không. dp[0][0] là true. Ở hàng 0, chuỗi rỗng chỉ khớp với tiền tố của mẫu nếu mọi phần tử trong đó đều có dấu sao, như z* hoặc a*b*.

Chữ cái hoặc dấu chấm tại p[j-1] phải khớp với s[i-1], và phần còn lại cũng phải khớp: ô chéo, dp[i-1][j-1]. Dấu sao với phần tử x = p[j-2] có hai cách chuyển. Không lấy bản sao nào thì bỏ x*: dp[i][j-2]. Lấy thêm một bản sao, khi x khớp với s[i-1], thì giữ nguyên x* để khớp với chuỗi ngắn hơn: dp[i-1][j], ô phía trên. Mỗi bản sao là một bước đi lên trong cột của dấu sao. Với sky và z*s.*y, cột của z*s.* có giá trị true với s nhờ không lấy bản sao nào, rồi với sk và sky, mỗi lần đi lên một bước.

Mỗi ô đọc hàng phía trên hoặc các ô bên trái, nên khi điền lần lượt từng hàng, các ô đó đã sẵn sàng.

Thuật toán

Tạo một bảng dp gồm (n+1) × (m+1) giá trị false và đặt dp[0][0] thành true.
Với j từ 2 đến m, đặt dp[0][j] thành true khi p[j-1] là dấu sao và dp[0][j-2] là true.
Với mỗi ô có i ≥ 1 và j ≥ 1, nếu p[j-1] là dấu sao, đặt ô đó thành dp[i][j-2] hoặc (p[j-2] khớp với s[i-1] và dp[i-1][j]).
Nếu không, đặt ô đó thành (p[j-1] khớp với s[i-1]) và dp[i-1][j-1].
Trả về dp[n][m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # dp[i][j]: do the first i letters of s match the first j characters of p?
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # an empty pattern matches an empty string
    for j in range(2, m + 1):
        # an empty string matches only patterns like x*y*z*
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more copy eats s[i-1]
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[n][m]

Chỉ giữ lại hai hàng

Ý tưởng

Hàng i chỉ đọc hai ô của hàng i-1, ô trên đường chéo và ô phía trên, cùng với ô của chính nó cách hai ô về bên trái. Hãy giữ hai mảng (array), prev và cur, rồi đổi chỗ chúng sau mỗi ký tự của s: không sao chép lần nào là cur[j-2], sao chép thêm một lần là prev[j], còn khớp thông thường là prev[j-1]. Bộ nhớ giảm từ khoảng 10^6 ô xuống còn hai hàng, mỗi hàng có 1001 ô. Bạn không thể đổi chỗ hai đầu vào để rút ngắn các hàng, vì chuỗi và mẫu đảm nhiệm những vai trò khác nhau.

Thuật toán

Điền hàng 0 của bảng vào prev.
Với mỗi chữ cái trong s, đặt cur[0] thành false và điền cur[1..m] theo các quy tắc của bảng, đọc prev ở hàng phía trên.
Hoán đổi prev và cur.
Trả về prev[m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # prev[j]: do the letters of s before the current one match the first j characters of p?
    prev = [False] * (m + 1)
    prev[0] = True  # row 0: the empty string
    for j in range(2, m + 1):
        prev[j] = p[j - 1] == "*" and prev[j - 2]  # only patterns like x*y*z* match it
    for i in range(1, n + 1):
        cur = [False] * (m + 1)  # cur[0] stays False: an empty pattern matches no letters
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = cur[j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and prev[j]  # one more copy eats s[i-1]
                cur[j] = zero or more
            else:
                cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
        prev = cur
    return prev[m]

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

Để dấu sao khớp với nhiều ký tự nhất có thể. a*a khớp với aaa, nhưng a* tham lam khớp hết cả ba ký tự, khiến chữ a cuối cùng không khớp.
Đọc dp[i-1][j-2] để khớp thêm một bản sao. Như vậy, dấu sao chỉ khớp tối đa một ký tự, nên aa so với a* cho kết quả false.
Để hàng 0 giữ giá trị false sau ô đầu tiên. Khi đó, b so với a*b không khớp, vì chữ b cần a* khớp với tiền tố rỗng.
So sánh s[i-1] với dấu sao thay vì phần tử của nó là p[j-2]. Khi đó, a so với a* không khớp.
Không đặt lại cur[0] thành false trong phiên bản dùng hai hàng. Sau khi hoán đổi, ô này có thể giữ giá trị true của hàng cơ sở, khiến aab so với b cho kết quả true.

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

Độ phức tạp thời gian của việc so khớp biểu thức chính quy là gì?

Lời giải dùng bảng chạy trong thời gian O(n × m) với chuỗi có độ dài n và mẫu có độ dài m, vì mỗi ô chỉ đọc tối đa hai ô khác. Lời giải cần O(n × m) bộ nhớ cho toàn bộ bảng, hoặc O(m) nếu dùng hai hàng. Đệ quy thông thường có thể mất thời gian theo hàm mũ với những mẫu có nhiều dấu sao.

Điều này khác gì so với khớp ký tự đại diện?

Trong phép so khớp ký tự đại diện, giống như trong các mẫu tên tệp, * đứng độc lập và khớp với bất kỳ chuỗi ký tự nào, còn ? khớp với một ký tự. Ở đây, * chỉ lặp lại phần tử đứng trước nó, còn mọi văn bản đều được biểu diễn bằng .*. Cả hai đều dùng một bảng trên các tiền tố, nhưng dấu sao ký tự đại diện đọc dp[i][j-1] hoặc dp[i-1][j].

Tại sao không dùng thư viện regex của ngôn ngữ đó?

Người phỏng vấn muốn thấy thuật toán (algorithm), chứ không phải lời gọi thư viện (library). Nhiều bộ máy regex cũng so khớp bằng cách quay lui (backtracking), kiểu đệ quy (recursion) chậm của cách tiếp cận đầu tiên, nên mười bản sao của a* theo sau bởi b khi so với một chuỗi dài gồm các chữ a có thể khiến chúng chạy trong nhiều phút. Bảng luôn hoàn tất trong O(n × m).

def isMatch(s, p):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "moon"
p = "mo*n"

Đầu ra mong đợi

true

Regular Expression Matching

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Ghép từ trái bằng đệ quy

Điền vào bảng tiền tố

Chỉ giữ lại hai hà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ự