Giả sử có một chuỗi S gồm các chữ cái thường, các chữ cái này tạo thành các nhóm liên tiếp của cùng một ký tự. Ví dụ, chuỗi "abbxxxxzyy" có các nhóm "a", "bb", "xxxx", "z" và "yy". Một nhóm được coi là nhóm lớn khi nó có 3 hoặc nhiều ký tự hơn. Ta muốn tìm vị trí bắt đầu và kết thúc của mọi nhóm lớn.
Ví dụ, nếu đầu vào là "abcdddeeeeaabbbcd", thì đầu ra sẽ là [[3,5],[6,9],[12,14]]
Để giải quyết, ta thực hiện các bước sau:
- ans := một danh sách mới
- csum := 0
- Với mỗi a, b trong nhóm các ký tự liên tiếp, thực hiện:
- grp := danh sách các phần tử được nhóm
- Nếu kích thước của grp >= 3, thì:
- Thêm danh sách (csum, csum + kích thước grp - 1) vào ans
- csum := csum + kích thước grp
- Trả về ans
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
from itertools import groupby class Solution: def largeGroupPositions(self, S): ans = [] csum = 0 for a, b in groupby(S): grp = list(b) if len(grp) >= 3: ans.append([csum, csum+len(grp)-1]) csum += len(grp) return ans ob = Solution() print(ob.largeGroupPositions("abcdddeeeeaabbbcd"))Đầu vào
"abcdddeeeeaabbbcd"
Đầu ra
[[3, 5], [6, 9], [12, 14]]