Given a string, the task is to write a Python program to get all possible slices for K number of slices.
Input : test_str = “Gfg4all”, K = 3
Output : [[‘G’, ‘f’, ‘g4all’], [‘G’, ‘fg’, ‘4all’], [‘G’, ‘fg4’, ‘all’], [‘G’, ‘fg4a’, ‘ll’], [‘G’, ‘fg4al’, ‘l’], [‘Gf’, ‘g’, ‘4all’], [‘Gf’, ‘g4’, ‘all’], [‘Gf’, ‘g4a’, ‘ll’], [‘Gf’, ‘g4al’, ‘l’], [‘Gfg’, ‘4’, ‘all’], [‘Gfg’, ‘4a’, ‘ll’], [‘Gfg’, ‘4al’, ‘l’], [‘Gfg4’, ‘a’, ‘ll’], [‘Gfg4’, ‘al’, ‘l’], [‘Gfg4a’, ‘l’, ‘l’]]
Explanation : All possible 3 slices for constructing string are returned.Input : test_str = “Gfg4all”, K = 2
Output : [[‘G’, ‘fg4all’], [‘Gf’, ‘g4all’], [‘Gfg’, ‘4all’], [‘Gfg4’, ‘all’], [‘Gfg4a’, ‘ll’], [‘Gfg4al’, ‘l’]]
Explanation : All possible 2 slices for constructing string are returned.
Method #1 : Using list comprehension + slicing + loop
In this, consecutive slices are computed incrementally starting from size 1. The last element is always split into 2 in all the ways in acc. to other strings.
Python3
# Python3 code to demonstrate working of# All possible slices for K length# Using list comprehension + string slicing + loop# initializing stringtest_str = "Gfg4all"# printing original stringprint("The original string is : " + str(test_str))# initializing number of slicesK = 3res = [[test_str]]for idx in range(K - 1): # slicing initial strings with difference sizes. res = [[*strt, end[:y], end[y:]] for *strt, end in res for y in range(1, len(end) - K + idx + 2)]# printing resultprint("All possible slices for K strings : " + str(res)) |
The original string is : Gfg4all All possible slices for K strings : [['G', 'f', 'g4all'], ['G', 'fg', '4all'], ['G', 'fg4', 'all'], ['G', 'fg4a', 'll'], ['G', 'fg4al', 'l'], ['Gf', 'g', '4all'], ['Gf', 'g4', 'all'], ['Gf', 'g4a', 'll'], ['Gf', 'g4al', 'l'], ['Gfg', '4', 'all'], ['Gfg', '4a', 'll'], ['Gfg', '4al', 'l'], ['Gfg4', 'a', 'll'], ['Gfg4', 'al', 'l'], ['Gfg4a', 'l', 'l']]
Method #2 : Using combinations() + zip() + list comprehension
In this, combinations is used to get all possible substrings for the ranges computed using slicing during iteration.
Python3
# Python3 code to demonstrate working of# All possible slices for K length# Using combinations() + zip() + list comprehensionfrom itertools import combinations# initializing stringtest_str = "Gfg4all"# printing original stringprint("The original string is : " + str(test_str))# initializing number of slicesK = 3# combinations used to perform all possible slicesres = [[test_str[idx: j] for idx, j in zip([None, *sub], [*sub, None])] for sub in combinations(range(1, len(test_str)), K - 1)]# printing resultprint("All possible slices for K strings : " + str(res)) |
The original string is : Gfg4all All possible slices for K strings : [['G', 'f', 'g4all'], ['G', 'fg', '4all'], ['G', 'fg4', 'all'], ['G', 'fg4a', 'll'], ['G', 'fg4al', 'l'], ['Gf', 'g', '4all'], ['Gf', 'g4', 'all'], ['Gf', 'g4a', 'll'], ['Gf', 'g4al', 'l'], ['Gfg', '4', 'all'], ['Gfg', '4a', 'll'], ['Gfg', '4al', 'l'], ['Gfg4', 'a', 'll'], ['Gfg4', 'al', 'l'], ['Gfg4a', 'l', 'l']]
Time Complexity: O(n2)
Space Complexity: O(n)
Approach#3: Using lambda
This approach uses a recursive approach with an anonymous function (lambda) to generate all possible slices of a string for a given number of slices.
Algorithm
1. The lambda function takes two parameters, the string to be sliced, and the number of slices required.
2. If the required number of slices is greater than 1, the function recursively generates all possible slices of the substring of the input string, starting from index i=1, and constructs a new list with the current slice added at the beginning.
3. The recursion continues until the number of required slices becomes 1, in which case the current slice is the only slice required, and it is returned as a list.
4. The final output is a list of all possible slices.
Python3
test_str = "Gfg4all"K = 3slices = lambda s, k: [[s[:i]] + j for i in range(1, len(s)) for j in slices(s[i:], k-1)] if k > 1 else [[s]]print(slices(test_str, K)) |
[['G', 'f', 'g4all'], ['G', 'fg', '4all'], ['G', 'fg4', 'all'], ['G', 'fg4a', 'll'], ['G', 'fg4al', 'l'], ['Gf', 'g', '4all'], ['Gf', 'g4', 'all'], ['Gf', 'g4a', 'll'], ['Gf', 'g4al', 'l'], ['Gfg', '4', 'all'], ['Gfg', '4a', 'll'], ['Gfg', '4al', 'l'], ['Gfg4', 'a', 'll'], ['Gfg4', 'al', 'l'], ['Gfg4a', 'l', 'l']]
Time Complexity: O(n^k), where n is the length of the input string, and k is the number of slices required. This is because the code generates all possible combinations of k slices, each of which can have a maximum length of n.
Space Complexity: O(n^k), as the number of possible combinations is the same as the number of elements in the output list. This can be a significant limitation for large values of k, as it can cause the program to run out of memory.
