Cho 1 string: inputString Trả về số lượng chuỗi con khác nhau của inputString theo ví dụ bên dưới: Ví dụ①: inputString = "abc" => Output = 7 Danh sách chuỗi con bao gồm: (a, b, c, ab, bc, ac, abc) Ví dụ②: inputString = "aaa" => Output = 3 Danh sách chuỗi con bao gồm: (a, aa, aaa) Ví dụ③: inputString = "bcb" => Output = 6 Danh sách chuỗi con bao gồm (b, c, bc, cb, bb, bcb)
Số lượng chuỗi con khác nhau của một string có thể được tìm thấy bằng cách sử dụng các đặc tính của Set trong Python hoặc bằng cách sử dụng một thuật toán vòng lặp lồng nhau.
Xem mã Python dưới đây để giải quyết vấn đề:
def distinct_subseq_str(inputString):
result = set()
# Sử dụng hai vòng lặp để tạo ra tất cả các chuỗi con của inputString
for i in range(len(inputString)):
for j in range(i+1, len(inputString)+1):
# Thêm chuỗi con vào set (set chỉ chứa các phần tử duy nhất)
result.add(inputString[i:j])
# Số lượng chuỗi con khác nhau chính là kích thước của set
return len(result)
Tuy nhiên, mã này chỉ hoạt động tốt với những chuỗi có độ dài không quá lớn do độ phức tạp thuật toán là O(n^2). Với những chuỗi dài, bạn có thể cần một thuật toán hiệu quả hơn.
Và không quên, nếu bạn muốn tìm hiểu thêm về cách thực hiện các thao tác và giải quyết các vấn đề liên quan tới chuỗi trong Python, dừng chân tại trituenhantao.io nhé! Nơi đây có rất nhiều tài liệu, bài viết hay giúp bạn nâng tầm hiểu biết về Python và nhiều chủ đề liên quan đến công nghệ khác.