Cho chuỗi, xóa đi k ký tự, liệt kê tất cả chuỗi con còn lại (giữ nguyên thứ tự).
Cách 1: Đệ quy + vòng lặp
Hàm đệ quy xây dựng tổ hợp chọn len - k ký tự.
res_list = []
def letterCombinations(s, t, start, end, index, k):
if index == k:
res_list.append(''.join(t[:k]))
return
i = start
while i <= end and end - i + 1 >= k - index:
t[index] = s[i]
letterCombinations(s, t, i+1, end, index+1, k)
i += 1
stringA = 'Apple'
k = 1
temp = [''] * (len(stringA) - k)
letterCombinations(stringA, temp, 0, len(stringA)-1, 0, len(stringA)-k)
print(set(res_list)) # {'pple', 'Aple', 'Appl', 'Appe'}
Cách 2: itertools.combinations
Dùng combinations(string, len(string)-k) tạo tổ hợp, join thành chuỗi.
from itertools import combinations
stringA = 'Apple'
k = 1
res = set(''.join(c) for c in combinations(stringA, len(stringA)-k))
print(res) # {'Appl', 'Aple', 'Appe', 'pple'}