Longest Common Prefix

Q: Độ phức tạp thời gian của Longest Common Prefix là gì?

Cả hai lần quét đều mất thời gian O(S) , trong đó S là tổng số chữ cái, và chỉ cần thêm O(1) bộ nhớ ngoài phần đáp án. Lần quét theo cột cũng bị giới hạn ở mức n × (L+1) với đáp án có độ dài L , nên sẽ dừng sớm khi các từ khác nhau gần phần đầu.

Q: Longest Common Prefix nên trả về gì khi không có tiền tố chung?

Chuỗi rỗng "" . Điều đó xảy ra ngay khi hai từ bắt đầu bằng các chữ cái khác nhau, như trong stack , queue và heap .

Q: Quét theo chiều ngang hay chiều dọc thì tốt hơn?

Cả hai đều có trường hợp xấu nhất như nhau, O(S) . Quét theo chiều dọc là lựa chọn an toàn hơn: cách này dừng ở cột đầu tiên có từ nào đó không khớp, còn quét theo chiều ngang có thể so sánh một tiền tố dài với nhiều từ trước khi một từ ở phía sau làm quá trình bị dừng sớm.

DễMảng và chuỗi

+10

Bạn nhận được một mảng các từ strs. Hãy trả về chuỗi dài nhất mà mọi từ đều bắt đầu bằng chuỗi đó. Nếu các từ không cùng bắt đầu bằng một chuỗi giống nhau, hãy trả về chuỗi rỗng "". Một từ được tính là tiền tố của chính nó, vì vậy nếu chỉ có một từ thì đáp án chính là từ đó.

Hàm

longestCommonPrefix(strs: string-array) → string

strsstring-array: các từ cần so sánh
Trả vềstring: tiền tố dài nhất mà tất cả các từ đều có chung, hoặc một chuỗi rỗng

Ràng buộc

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Mỗi từ chỉ chứa các chữ cái tiếng Anh viết thường.

Ví dụ

Đầu vào: strs = ["interview", "internet", "interval", "internal"]
Đầu ra: "inter"
Giải thích: Cả bốn từ đều bắt đầu bằng inter. Ở vị trí tiếp theo, interview và interval có chữ v, còn internet và internal có chữ n, nên tiền tố dừng ở đó.

Đầu vào: strs = ["stack", "queue", "heap"]
Đầu ra: ""
Giải thích: Các từ bắt đầu bằng s, q và h. Chúng khác nhau ngay ở chữ cái đầu tiên, nên đáp án là chuỗi rỗng.

Đầu vào: strs = ["prefix", "pre", "prepare"]
Đầu ra: "pre"
Giải thích: pre là từ ngắn nhất và hai từ còn lại đều bắt đầu bằng từ này, nên đây là toàn bộ đáp án. Tiền tố chung không bao giờ dài hơn từ ngắn nhất.

Câu hỏi mở rộng

Giả sử danh sách không thay đổi và có nhiều từ cần truy vấn. Bạn sẽ tìm tiền tố chung dài nhất giữa mỗi từ cần truy vấn và một từ trong danh sách như thế nào mà không phải quét lại danh sách?

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ột chữ cái chỉ thuộc đáp án nếu mọi từ đều có chữ cái đó ở cùng vị trí, và đáp án kết thúc ở vị trí đầu tiên mà một từ có chữ cái khác hoặc hết chữ cái. Cả hai cách đều đọc từng chữ cái của các từ theo thứ tự khác nhau. Duyệt theo cột sẽ dừng ở điểm bất đồng đầu tiên.

Rút ngắn tiền tố từng từ một

Ý tưởng

Giả sử toàn bộ từ đầu tiên là đáp án. Rút gọn từ đó thành phần chung với từ thứ hai, rồi đến từ thứ ba, cứ tiếp tục như vậy. Tiền tố chung của nhiều từ là tiền tố chung của hai từ đầu tiên, sau đó là tiền tố chung của phần đó và từ thứ ba: mỗi bước chỉ có thể giữ nguyên hoặc rút ngắn tiền tố. Ví dụ 1, ứng viên chuyển từ interview thành inter sau từ thứ hai và giữ nguyên như vậy.

Mỗi chữ cái được so sánh nhiều nhất một lần, nên độ phức tạp thời gian là O(S) với S chữ cái tổng cộng. Điểm yếu là thứ tự: với 200 từ dài 200 chữ cái, trong đó chỉ từ cuối cùng khác từ đầu tiên ở chữ cái đầu, bạn thực hiện gần 40.000 phép so sánh trước khi từ cuối cùng rút tiền tố xuống còn rỗng.

Thuật toán

Đặt prefixLen bằng độ dài của strs[0].
Với mỗi từ còn lại, đếm số chữ cái ở đầu từ trùng với strs[0], tối đa bằng prefixLen.
Đặt prefixLen bằng số đó và dừng sớm nếu giá trị này bằng 0.
Trả về strs[0] gồm prefixLen chữ cái đầu tiên.

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

So sánh từng cột

Ý tưởng

Đọc các từ như một bảng, mỗi lần đọc một cột. Lấy ký tự của strs[0] ở cột hiện tại rồi kiểm tra xem mọi từ khác có cùng ký tự ở vị trí đó không. Khi một từ không khớp lần đầu tiên hoặc quá ngắn để có cột đó, đáp án là phần của strs[0] tính đến cột đó.

Đáp án chính là dãy cột mà tất cả các từ đều khớp, và vòng lặp này đi qua dãy đó từ trái sang phải rồi dừng ở vị trí không còn khớp. Nếu không có vị trí nào không khớp, đáp án là strs[0].

Với n từ và đáp án có độ dài L, vòng lặp thực hiện nhiều nhất n × (L+1) lần kiểm tra, cũng là O(S). Trong trường hợp chỉ từ cuối cùng trong 200 từ khác ký tự đầu tiên, vòng lặp dừng sau 199 lần so sánh.

Thuật toán

Gọi first là strs[0].
Với mỗi cột col từ 0 đến độ dài của first trừ đi một, đọc first[col].
Với mỗi từ còn lại, nếu từ đó không có ký tự ở col hoặc ký tự đó khác, hãy trả về first gồm col ký tự đầu tiên.
Nếu mọi cột đều trùng khớp, hãy trả về first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

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

Đọc vượt quá cuối một từ ngắn hơn. Trong prefix, pre, prepare, cột 3 có trong prefix nhưng không có trong pre; hãy kiểm tra độ dài trước khi đọc ký tự.
Chỉ so sánh từ đầu tiên và từ cuối cùng mà không sắp xếp. Trong abc, xbd, abd, hai từ đó cùng có ab, nhưng xbd không khớp ở cột 0 và đáp án là chuỗi rỗng.
Trả về null hoặc một giá trị giữ chỗ khi không có gì chung. Đáp án là chuỗi rỗng.
Quên rằng một từ đơn lẻ là tiền tố của chính nó: chỉ có algorithm thì trả về algorithm.
Thêm từng ký tự một vào một chuỗi bất biến. Khi đó, đáp án dài 200 ký tự sẽ tốn 200 lần sao chép; hãy lưu độ dài rồi cắt từ đầu tiên một lần.

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

Độ phức tạp thời gian của Longest Common Prefix là gì?

Cả hai lần quét đều mất thời gian O(S), trong đó S là tổng số chữ cái, và chỉ cần thêm O(1) bộ nhớ ngoài phần đáp án. Lần quét theo cột cũng bị giới hạn ở mức n × (L+1) với đáp án có độ dài L, nên sẽ dừng sớm khi các từ khác nhau gần phần đầu.

Bạn có thể tìm tiền tố chung dài nhất bằng cách sắp xếp các từ không?

Đúng. Theo thứ tự bảng chữ cái, mọi từ nằm giữa từ đầu tiên và từ cuối cùng đều bắt đầu bằng phần chung của hai từ đó, nên chỉ cần so sánh hai từ này là tìm được đáp án. Việc sắp xếp so sánh khoảng n log n cặp từ, tốn công hơn một lượt duyệt, nhưng code ngắn gọn.

Longest Common Prefix nên trả về gì khi không có tiền tố chung?

Chuỗi rỗng "". Điều đó xảy ra ngay khi hai từ bắt đầu bằng các chữ cái khác nhau, như trong stack, queue và heap.

Quét theo chiều ngang hay chiều dọc thì tốt hơn?

Cả hai đều có trường hợp xấu nhất như nhau, O(S). Quét theo chiều dọc là lựa chọn an toàn hơn: cách này dừng ở cột đầu tiên có từ nào đó không khớp, còn quét theo chiều ngang có thể so sánh một tiền tố dài với nhiều từ trước khi một từ ở phía sau làm quá trình bị dừng sớm.

def longestCommonPrefix(strs):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

strs = ["interview", "internet", "interval", "internal"]

Đầu ra mong đợi

"inter"