Python – Split Numeric String into K digit integers

Given a String, convert it to K digit integers

Input : test_str = ‘457336’, K = 2 

Output : [45, 73, 36] 

Explanation : Divided in 2 digit integers. 

Input : test_str = ‘457336’, K = 3 

Output : [457, 336] 

Explanation : Divided in 3 digit integers.

Method #1 : Using int() + slice + loop

In this, we iterate for string and perform slicing till K digits and then perform task of conversion to integer using int().

The original string is : 457336842
Converted number list : [457, 336, 842]

Time Complexity: O(n), where n is the length of the input list. 
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list “test_list”. 

Method #2 : Using list comprehension + int() + slicing

Similar method to above, just a shorthand to solve this problem.

The original string is : 457336842
Converted number list : [457, 336, 842]

Time Complexity: O(n)

Auxiliary Space: O(n)

Method #3 : Using regex:

1. Import the re module to use regular expressions.
2. Define the input string test_str and the number of digits K in each substring.
3. Use re.findall() to find all substrings of test_str that contain exactly K digits.
4. Use . to match any character, and * to match zero or more occurrences of the preceding character or group.
   The pattern .*K matches any K characters.
5. Use re.findall() to find all substrings in test_str that match the pattern.
6. re.findall() returns a list of strings, where each string has K characters.
7. Use map() to convert each substring in the resulting list to an integer.
8. map() applies the int() function to each element in the list.
9. The resulting list contains integers instead of strings.
10. Store the resulting list of integers in res.
11. Print the list res.

The original string is : 457336842
Converted number list : [457, 336, 842]

The time complexity : O(n/K), where n is the length of the input string test_str. The re.findall() method iterates over the input string in steps of K, and each iteration takes constant time to find the K-character substring. Therefore, the time complexity of re.findall() is O(n/K), and the overall time complexity of the algorithm is also O(n/K).

The auxiliary space :O(n/K) because the resulting list contains n/K elements, each with K digits. The space required to store each element is proportional to K, so the overall space complexity is proportional to n/K * K, which simplifies to O(n/K). Additionally, the re.findall() method may allocate additional memory to store the intermediate results of its search, but this memory usage is also proportional to n/K and is dominated by the space required to store the resulting list.

Method 4: Using recursion

Step-by-step approach 

• Define a recursive function split_string that takes a string s and an integer k as arguments.
• The base case of the recursive function is when the input string s is empty. In this case, return an empty list [].
• In the recursive case, split the input string s into a K digit substring and the rest of the string using slicing s[:k] and s[k:], respectively.
• Convert the K digit substring to an integer using int() and append it to the result of the recursive call to split_string() on the rest of the string.
• Call the recursive function split_string with the input string test_str and substring length K as arguments, and store the result in the variable res.
• Print the result of the function using print(“Converted number list : ” + str(res)).

The original string is : 457336842
Converted number list : [457, 336, 842]

Time complexity: O(n/K) where n is the length of the input string.
Auxiliary space: O(n/K) in the worst case.