Cách tìm các ký tự duy nhất trong một chuỗi trong python

Hướng dẫn này sẽ chỉ ra các cách tiếp cận khác nhau để tìm ký tự duy nhất đầu tiên trong một chuỗi nhất định. Chẳng hạn, kết quả phải là "n" nếu chuỗi đã cho là "stringstutorial" và "S" nếu chuỗi đã cho là "StringsTutorial"

Giải trình

Đầu vào. "hướng dẫn về dây"

Giải trình

Bước 1. Tạo danh sách tần số của các ký tự cho chuỗi đã cho

tần số ['s'] = 2

tần số ['t'] = 3

tần số ['r'] = 2

tần số ['i'] = 2

tần số ['n'] = 1

tần số ['g'] = 1

tần số ['u'] = 1

tần số ['o'] = 1

tần số ['a'] = 1

tần số ['l'] = 1

Bước 2. Tìm ký tự đầu tiên có tần số đơn vị

Tạo bản đồ băm tần số

Nếu một ký tự chỉ xuất hiện một lần trong chuỗi đã cho, ký tự đó được coi là ký tự không lặp lại. Tính tần suất của mỗi chữ cái trong chuỗi chuỗi và xác định chữ cái nào có tần số bằng 1 là các bước để định vị các ký tự duy nhất đó. Bản đồ băm, ánh xạ các ký tự theo tần số tương ứng của chúng và cho phép chúng tôi sửa đổi đồng thời tần suất của các ký tự mà chúng tôi đã gặp trong thời gian không đổi, là một công cụ hiệu quả cho công việc này. Trong hệ thống ASCII, 256 ký tự duy nhất là giới hạn. Vì vậy, độ dài tối đa của bản đồ băm là 256. Đọc lại chuỗi và chữ cái đầu tiên có tần số bằng một là giải pháp

thuật toán

  1. Tạo bản đồ băm để liên kết từng ký tự với tần số của nó
  2. Sử dụng một con trỏ để điều hướng chuỗi đầu vào
  3. Sửa đổi số ký tự hiện có trong bản đồ băm
  4. Tiếp theo, đi qua chuỗi một lần nữa để xác định xem ký tự hiện tại có tần số = 1 hay không
  5. Tiếp tục đi ngang nếu tần số vượt quá 1
  6. Nếu không, kết thúc vòng lặp và xuất ký tự hiện tại làm giải pháp

Mã số

đầu ra

The first unique character is n

Tìm ký tự duy nhất bằng cách duyệt qua chuỗi chỉ một lần

Phương thức chính yêu cầu thời gian chạy O(n), mặc dù chúng ta có thể làm cho nó nhanh hơn trong ứng dụng. Mảng đếm được xây dựng trong bước đầu tiên của quy trình bằng cách duyệt qua văn bản lặp đi lặp lại trong thời gian chạy O(n). Bước này có ý nghĩa. Tuy nhiên, phần thứ hai, nơi chúng tôi phát lại trình lặp không lặp lại ban đầu của chuỗi, không phải là một ý kiến ​​hay

Chuỗi được dự đoán lâu hơn nhiều so với bộ ký tự của chúng tôi trong hoàn cảnh thực tế. Hãy xem xét các chuỗi DNA, có thể chứa hàng tỷ chữ cái và chỉ có một bảng chữ cái gồm bốn chữ cái. Điều gì xảy ra nếu ký tự duy nhất ở cuối chuỗi?

Tạo Hash Map và Traversing String Once

Thay vì sử dụng bản đồ băm, hãy tạo một mảng tần số có độ dài của danh sách ký tự là 256. Bằng cách thêm vào mảng tần suất, chúng tôi có thể lưu trữ không chỉ tần suất mà còn cả vị trí xuất hiện đầu tiên của chữ cái, chẳng hạn như (5, 36) cho chữ cái, cho biết rằng nó đã được ghi năm lần và ban đầu xuất hiện ở vị trí 36. Để xác định vị trí ký tự duy nhất đầu tiên, chúng ta chỉ cần quét mảng tần số chứ không phải chuỗi. Dưới đây là việc thực hiện ý tưởng này

Mã số

đầu ra

First unique character is n

Tạo danh sách tần số và lặp lại chỉ một lần

Tạo danh sách tần suất tối đa 256 ký tự. Chúng ta có thể khởi tạo tất cả các mục trong danh sách này thành -1. Chúng tôi sẽ lặp lại các ký tự của chuỗi và kiểm tra xem các phần tử danh sách có ký tự cụ thể này có chỉ số là 1 hay không. Nếu nó là -1, chúng ta sẽ đổi nó thành j;

Tất cả các ký tự lặp lại cuối cùng sẽ được thay đổi thành -2, trong khi tất cả các ký tự duy nhất sẽ vẫn giữ nguyên chỉ mục mà chúng xuất hiện lần đầu. Chúng ta có thể nhanh chóng tìm ra chỉ mục nhỏ nhất hoặc ban đầu bằng cách lặp lại tất cả các ký tự duy nhất

Mã số

đầu ra

The first unique character is n

Sử dụng các Hàm dựng sẵn của Python

Sử dụng hàm Counter() để xác định tần số của tất cả các ký tự

Đi qua chuỗi và tìm phần tử nào có tần số 1. In ký tự duy nhất và phá vỡ vòng lặp ở đó

Mã số

đầu ra

The first unique character is: n

Sử dụng hàm find() của chuỗi

Sau chữ cái hiện tại, tra cứu từng chữ cái tiếp theo. Nếu nó trả về -1, điều đó có nghĩa là chữ cái chỉ xuất hiện một lần, đó là chỉ số hiện tại

Mã số

đầu ra

The first unique character is: n

Sử dụng hàm đếm()

Nếu số đếm () của một ký tự trong một chuỗi là 1, điều đó cho biết ký tự đó là duy nhất và không lặp lại. Chúng tôi sẽ ngắt vòng lặp và in ký tự duy nhất đầu tiên mà chúng tôi tìm thấy

Giả sử chúng ta có một chuỗi và chúng ta phải tìm ký tự duy nhất đầu tiên trong chuỗi. Vì vậy, nếu chuỗi giống như "người", chữ cái đầu tiên có số lần xuất hiện là 'o'. Vì vậy, chỉ mục sẽ được trả về, đó là 2 ở đây. Nếu không có ký tự nào thì trả về -1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • tạo một bản đồ tần số
  • đối với mỗi ký tự c trong chuỗi, hãy làm
    • nếu c không có tần số, hãy chèn nó vào tần số và đặt giá trị 1
    • mặt khác, tăng số lượng trong tần số
  • Quét bản đồ tần số, nếu giá trị của một khóa cụ thể là 1, thì trả về khóa đó, nếu không thì trả về -1

Ví dụ

Chúng ta hãy xem triển khai sau đây để hiểu rõ hơn -

Bản thử trực tiếp

class Solution(object):
   def firstUniqChar(self, s):
      """
      :type s: str
      :rtype: int
      """
      frequency = {}
      for i in s:
         if i not in frequency:
            frequency[i] = 1
         else:
            frequency[i] +=1
      for i in range(len(s)):
         if frequency[s[i]] == 1:
            return i
      return -1
ob1 = Solution()
print(ob1.firstUniqChar("people"))
print(ob1.firstUniqChar("abaabba"))

Đầu vào

"people"
"abaabba"

đầu ra

2
-1

Cách tìm các ký tự duy nhất trong một chuỗi trong python


Cách tìm các ký tự duy nhất trong một chuỗi trong python

Làm cách nào để tìm số ký tự duy nhất trong tệp văn bản Python?

fh = open('my. txt','r'). read() unique_chars = set(fh) len(unique_chars) # cho độ dài.

Làm cách nào để tìm tất cả các ký tự không lặp lại trong một chuỗi bằng Python?

Thuật toán .
Bước 1. - lưu trữ chuỗi trong một biến giả sử Chuỗi
Bước 2. - hãy để nó là "prepinsta"
Bước 3. - Bắt đầu lặp qua chuỗi
Bước 4. - Khởi tạo biến đếm
Bước 5. - Một lần nữa bắt đầu lặp qua cùng một chuỗi
Bước 6. - Biến đếm tăng dần khi tìm thấy ký tự trong chuỗi

Làm cách nào để kiểm tra xem có các chữ cái lặp lại trong chuỗi Python không?

Tạo một chuỗi và lưu trữ nó trong một biến. Để so sánh ký tự đã chọn với các ký tự còn lại trong chuỗi, một vòng lặp bên trong sẽ được sử dụng. Nếu một trận đấu được tìm thấy, số lượng được tăng lên 1. Nếu số ký tự nhiều hơn 1 sau khi vòng lặp bên trong kết thúc, thì sẽ có các ký tự trùng lặp trong chuỗi .