Xác định xem một chuỗi có tất cả các ký tự duy nhất python

Tôi vừa hoàn thành CS 325 - Phân tích thuật toán vài tuần trước và vì tôi không muốn mất nhiều kiến ​​thức đã học được trong lớp đó, tôi đã quyết định bắt đầu xem qua một số cuốn sách mà tôi có về các câu hỏi về cấu trúc dữ liệu và thuật toán.

Tôi có lẽ sẽ bắt đầu cố gắng viết blog nhiều hơn về những câu hỏi thú vị [với tôi] mà tôi bắt gặp trong quá trình tự học này.

Một vấn đề mà tôi đã giải quyết gần đây và thực sự thích có tiêu đề "Là duy nhất" và muốn tôi tạo một thuật toán để xác định xem một chuỗi có tất cả các ký tự duy nhất hay không

Cách tiếp cận chung của tôi để giải quyết các vấn đề như thế này là giải quyết chúng trên giấy trước khi cố gắng viết bất kỳ mã nào

Cách tiếp cận đầu tiên đến với tôi là chỉ lặp qua từng ký tự trong chuỗi, lưu trữ từng ký tự trong danh sách. Trong khi lặp, nếu ký tự đã có trong danh sách, thì hàm sẽ trả về False vì điều đó cho biết rằng ký tự đã được gặp trước đó và do đó không phải là duy nhất

Một điều khác mà tôi đã nghĩ thoáng qua, đó là nếu chuỗi chứa nhiều ký tự hơn trong bất kỳ bộ ký tự nào mà chúng ta đang xử lý, thì hàm sẽ trả về False vì không thể có 201 ký tự duy nhất của một chuỗi trong một bộ ký tự mà

Mã Python thực tế sau đó tôi đã viết để tự giải quyết vấn đề bên dưới. Tôi đã chọn không xử lý việc trả về False cho một chuỗi có nhiều ký tự hơn bộ ký tự vì tôi cảm thấy như sẽ không có cách nào để xác định tôi đang xử lý bộ ký tự nào

def is_unique[input]:
  char_seen = []
  for char in input:
    if char in char_seen:
      return False
    char_seen.append[char]
  return True

Tôi khá hài lòng với giải pháp của mình và sau đó tôi tò mò đọc giải pháp lý tưởng trong sách để tìm ra cách tiếp cận lý tưởng là gì

Một điều cần lưu ý là giải pháp lý tưởng sẽ không bao giờ tốt hơn O[n] bởi vì chúng ta phải kiểm tra mọi ký tự trong chuỗi đầu vào trước khi biết liệu mỗi ký tự có phải là duy nhất hay không. Không có cách nào để vượt qua điều đó

Mặc dù vậy, mã của tôi ở trên là một ví dụ về nơi các tính năng cấp cao của Python thực sự có thể khiến bạn gặp khó khăn nếu bạn không cẩn thận. Ý tôi là tôi đang sử dụng sức mạnh của toán tử in trong python để giúp tôi kiểm tra xem một phần tử có trong danh sách không. Tôi đã nghĩ rằng mã ban đầu của tôi ở trên là

def is_unique[n]:
  char_seen = []
  for char in n:
    for i in char_seen:
      if char == i:
        return False
    char_seen.append[char]
  return True

0 Trong đầu, tôi nghĩ không sao. Tôi chỉ đơn giản là kiểm tra xem một phần tử có trong danh sách hay không và thực hiện điều đó cho từng phần tử trong danh sách. Đó là 1 thao tác cho mỗi n phần tử trong danh sách đầu vào, vì vậy đó là O[n]

Nhưng điều này có thực sự được coi là một thao tác/bước trong phân tích của tôi không? . https. //wiki. con trăn. org/moon/Độ phức tạp của thời gian

Một điều khác tôi có thể tự làm là giải quyết vấn đề mà không cần sử dụng toán tử in

def is_unique[n]:
  char_seen = []
  for char in n:
    for i in char_seen:
      if char == i:
        return False
    char_seen.append[char]
  return True

Khi chúng ta tránh sức mạnh của toán tử in để kiểm tra xem các phần tử có tồn tại trong danh sách hay không, sẽ dễ dàng thấy rằng mã ban đầu của tôi thực sự là O[n^2] vì tôi đã lồng các vòng lặp for được điều khiển bởi biến đầu vào n

Vì vậy, có cách tiếp cận nào tốt hơn có thể mang lại cho chúng tôi thời gian chạy trong trường hợp xấu nhất tốt hơn O[n^2] không?

Cách tiếp cận mà cuốn sách đề xuất là chúng tôi sử dụng bảng băm [từ điển trong Python] để lưu trữ tất cả các ký tự có thể và sau đó có một boolean để cho biết liệu giá trị đó đã được gặp trước đó chưa. Ví dụ: giả sử chúng tôi có một bộ bốn ký tự đặc biệt của

def is_unique[n]:
  char_seen = []
  for char in n:
    for i in char_seen:
      if char == i:
        return False
    char_seen.append[char]
  return True

1, đây là cấu trúc dữ liệu bảng băm của chúng tôi có thể trông như thế nào

'a' : False,
'b' : False,
'c' : False,
'd' : False

Bây giờ, chúng ta có thể sử dụng thời gian tra cứu nhanh của bảng băm để tránh phải lặp qua danh sách. Độ phức tạp không gian trong trường hợp xấu nhất của phương pháp này cũng thấp hơn vì chúng tôi chỉ lưu trữ một giá trị boolean cho mỗi ký tự trong bộ ký tự, thay vì lưu trữ n ký tự trong danh sách

Cách tiếp cận mới này trông giống như O[n] của nó. Nhưng nó thực sự nhanh hơn thế. Bạn có thể lập luận rằng độ phức tạp thời gian mới sẽ là O[1] [thời gian không đổi] vì thuật toán sẽ không bao giờ lặp qua nhiều hơn c ký tự, trong đó c là số ký tự trong bộ ký tự. c là một hằng số cố định và ví dụ: nếu chúng ta có 4 ký tự trong bộ ký tự của mình thì độ phức tạp về thời gian sẽ là O[4]. Do cách ký hiệu Big Oh hoạt động, điều này sẽ giảm xuống còn O[1]

Dưới đây là mã tôi đã viết sử dụng phương pháp nhanh hơn này. Đối với ví dụ này, tôi giả định rằng chúng ta có một bộ ký tự nhỏ đặc biệt chỉ bao gồm các ký tự

def is_unique[n]:
  char_seen = []
  for char in n:
    for i in char_seen:
      if char == i:
        return False
    char_seen.append[char]
  return True

1

def is_unique[n]:

  char_set = {'a':False,
           'b':False,
           'c':False,
           'd':False}

  for char in n:
    if char_set[char] == False:
       char_set[char] = True
    else:
      return False
  return True

Vâng, đó là nó cho bài đăng nhanh này

Các lớp tôi sẽ bắt đầu học kỳ Mùa đông này tại Bang Oregon là Hợp ngữ và Kỹ thuật phần mềm 1. Vì vậy, mong đợi để xem thêm bài viết về các chủ đề đó. Tôi cũng đang làm việc chăm chỉ [khi có thời gian] trên một ứng dụng web dự án cá nhân mà tôi dự định sẽ triển khai sớm.