Given a string that has set of words and spaces, write a program to move all spaces to front of string, by traversing the string only once. Examples:
Input : str = "Lazyroar for Lazyroar" Output : str = " neveropen" Input : str = "move these spaces to beginning" Output : str = " movethesespacestobeginning" There were four space characters in input, all of them should be shifted in front.
This problem has existing solution, please refer Move spaces to front of string in single traversal link. We will solve this problem quickly in Python using List Comprehension.
Approach 1:
- Traverse input string and create a string without any space character using list comprehension.
- Now to know how many space characters were there in original string just take a difference of length of original string and new string.
- Now create another string and append space characters at the beginning.
Implementation
Python3
# Function to move spaces to front of string # in single traversal in Python def moveSpaces(input): # Traverse string to create string without spaces noSpaces = [ch for ch in input if ch!=' '] # calculate number of spaces space= len(input) - len(noSpaces) # create result string with spaces result = ' '*space # concatenate spaces with string having no spaces result = '"'+result + ''.join(noSpaces)+'"' print (result) # Driver program if __name__ == "__main__": input = 'Lazyroar for Lazyroar' moveSpaces(input) |
" neveropen"
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach 2 : Using count() and replace() methods
Implementation
Python3
# Function to move spaces to front of string# in single traversal in Pythondef moveSpaces(input): c=input.count(' ') input=input.replace(' ','') input=' '*c+input print(input)# Driver programif __name__ == "__main__": input = 'Lazyroar for Lazyroar' moveSpaces(input) |
neveropen
Time complexity: O(n), where n is the length of the input string.
Auxiliary space: O(n), as the function creates a new string of length n (where n is the length of the input string) to store the modified string with spaces moved to the front.
Approach 3 : Using operator.countOf() and replace() methods
Python3
# Function to move spaces to front of string# in single traversal in Pythondef moveSpaces(input): import operator c=operator.countOf(input,' ') input=input.replace(' ','') input=' '*c+input print(input)# Driver programif __name__ == "__main__": input = 'Lazyroar for Lazyroar' moveSpaces(input) |
neveropen
Time Complexity : O(N)
Auxiliary Space : O(1)
Approach 5: Using join() and split() methods
- Split the input string into a list of words using the split() method.
- Join the list of words using the join() method to form a new string without any space characters.
- Append the required number of space characters at the beginning of the modified string.
- Return the modified string.
Python3
def moveSpaces(input): words = input.split() modified_str = ''.join(words) num_spaces = len(input) - len(modified_str) modified_str = ' ' * num_spaces + modified_str return modified_str# Driver programif __name__ == "__main__": input_str = 'Lazyroar for Lazyroar' print(moveSpaces(input_str)) |
neveropen
Time complexity: O(n), where n is the length of the input string.
Auxiliary space: O(n), where n is the length of the input string (to store the list of words and the modified string).
Approach 6: Using regular expressions
Algorithm:
- The input string is passed to the function moveSpaces() as input_str.
- The re.sub() method is used to replace all occurrences of a space with an empty string in the input_str. The modified string is then stored in the variable modified_str.
- The number of spaces in the original input string is calculated by taking the difference between the length of input_str and the length of modified_str.
- The required number of spaces is added at the beginning of the modified string using the multiplication operator and the ‘ ‘ (space) character. The modified
- string is then stored back in the variable modified_str.
- The modified string is returned as the output of the function.
- Finally, the moveSpaces() function is called with the input string ‘Lazyroar for Lazyroar’ and the output is printed.
Python3
import redef moveSpaces(input_str): # Replace all occurrences of space with empty string modified_str = re.sub(' ', '', input_str) # Get the number of spaces in the original string num_spaces = len(input_str) - len(modified_str) # Add the required number of spaces at the beginning of the modified string modified_str = ' ' * num_spaces + modified_str return modified_strinput_str = 'Lazyroar for Lazyroar'print(moveSpaces(input_str)) |
neveropen
Time complexity: O(n), where n is the length of the input string. The regular expression re.sub() method used in this approach has a time complexity of O(n), where n is the length of the input string.
Space complexity: O(n), where n is the length of the input string. This is because the re.sub() method creates a new string with all spaces removed, which is stored in memory before being used to calculate the number of spaces in the original string and add the required number of spaces at the beginning of the modified string.
