Reverse each word in a string

The problem is to reverse individual words in a given string. Given a sentence, we need to reverse each word in the sentence while maintaining the order of the words.

Example

Let's say we have the following input string: "This is a simple words". After reversing individual words, the output should be "sihT si a elpmis sdrow".

Idea to Solve the Problem

To reverse individual words in a string, we can use a stack to store characters of each word in the sentence. We iterate through the input string character by character and push each character into the stack until we encounter a space, which indicates the end of the current word. Once we encounter a space, we pop characters from the stack and append them to the result string, effectively reversing the word. We continue this process until we reach the end of the input string.

Algorithm

1. Define a custom stack data structure with push, pop, is_empty, and peek operations.
2. Create a function reversing_word that takes the input string as input and returns the string with individual words reversed.
3. Initialize an empty result string to store the final output.
4. Iterate through the input string character by character.
5. If the character is not a space, push it into the stack.
6. If the character is a space or the end of the input string, it means we have reached the end of the current word. In this case:
   • Pop characters from the stack and append them to the result string until the stack is empty. This will reverse the word.
   • If it's not the end of the input string, append a space to the result string to separate the reversed words.
7. Continue the iteration until the end of the input string is reached.
8. Return the result string containing the individual words reversed.

Pseudocode

FUNCTION reversing_word(text):
    result = "" // Initialize an empty result string
    stack = MyStack() // Create a new stack
    
    FOR i = 0 to length of text - 1:
        IF text[i] is not a space:
            // Push non-space characters into the stack
            stack.push(text[i])
        ELSE:
            // When a space is encountered, pop characters from stack
            // and append them to the result string until the stack is empty
            WHILE stack is not empty:
                result += stack.peek()
                stack.pop()
            // If it's not the end of the input string, append a space to separate words
            IF i is not length of text - 1:
                result += " "
    
    RETURN result

Code Solution

• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// Java program
// Reverse individual words of the sentence

//Stack Node
class Node
{
	public char data;
	public Node next;
	public Node(char data)
	{
		this.data = data;
		this.next = null;
	}
}
//Define custom stack and its operation
class MyStack
{
	public Node top;
	public MyStack()
	{
		this.top = null;
	}
	//Add a new element in stack
	public void push(char data)
	{
		//Make a new stack node
		Node new_node = new Node(data);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			System.out.print("Memory overflow\n");
		}
	}
	//remove a top element in stack
	public void pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	//check that whether stack is empty or not
	public boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public char peek()
	{
		if (this.top != null)
		{
			return this.top.data;
		}
		else
		{
			return ' ';
		}
	}
}
class ReverseStringWord
{
	// Reverse the given string words
	public String reversing_word(String text)
	{
		int size = text.length();
		//Auxiliary variable which is used to store result of string
		String result = "";
		//Create an stack
		MyStack stack = new MyStack();
		// Add element into stack
		for (int i = 0; i < size; i++)
		{
			if (text.charAt(i) == ' ')
			{
				// iterating the stack elements until if not empty
				while (stack.is_empty() == false)
				{
					//Get top element
					result += stack.peek();
					//remove current top
					stack.pop();
				}
				result += " ";
			}
			else
			{
				//Add element into stack
				stack.push(text.charAt(i));
			}
		}
		// When last words are exist in stack
		while (stack.is_empty() == false)
		{
			//Get top element
			result += stack.peek();
			//remove current top
			stack.pop();
		}
		return result;
	}
	public static void main(String[] args)
	{
		ReverseStringWord obj = new ReverseStringWord();
		String text = "This is a simple words";
		System.out.print(" Before Reverse : [" + text + "]");
		text = obj.reversing_word(text);
		System.out.print("\n After Reverse  : [" + text + "]");
		text = "It's to good ";
		System.out.print("\n Before Reverse : [" + text + "]");
		text = obj.reversing_word(text);
		System.out.print("\n After Reverse  : [" + text + "]");
	}
}

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

//Include header file
#include <iostream>
#include<string.h>

using namespace std;

// C++ program
// Reverse individual words of the sentence

//Stack Node
class Node
{
	public: 
    char data;
	Node *next;
	Node(char data)
	{
		this->data = data;
		this->next = NULL;
	}
};
//Define custom stack and its operation
class MyStack
{
	public: 
    Node *top;
	MyStack()
	{
		this->top = NULL;
	}
	//Add a new element in stack
	void push(char data)
	{
		//Make a new stack node
		Node *new_node = new Node(data);
		if (new_node != NULL)
		{
			new_node->next = this->top;
			this->top = new_node;
		}
		else
		{
			cout << "Memory overflow\n";
		}
	}
	//remove a top element in stack
	void pop()
	{
		if (this->top != NULL)
		{
			this->top = this->top->next;
		}
	}
	//check that whether stack is empty or not
	bool is_empty()
	{
		if (this->top != NULL)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	char peek()
	{
		if (this->top != NULL)
		{
			return this->top->data;
		}
		else
		{
			return ' ';
		}
	}
};
class ReverseStringWord
{
	public:
		// Reverse the given string words
		string reversing_word(string text)
		{
			int size = text.size();
			//Auxiliary variable which is used to store result of string
			string result = "";
			//Create an stack
			MyStack stack = MyStack();
			// Add element into stack
			for (int i = 0; i < size; i++)
			{
				if (text[i] == ' ')
				{
					// iterating the stack elements until if not empty
					while (stack.is_empty() == false)
					{
						//Get top element
						result += stack.peek();
						//remove current top
						stack.pop();
					}
					result += " ";
				}
				else
				{
					//Add element into stack
					stack.push(text[i]);
				}
			}
			// When last words are exist in stack
			while (stack.is_empty() == false)
			{
				//Get top element
				result += stack.peek();
				//remove current top
				stack.pop();
			}
			return result;
		}
};
int main()
{
	ReverseStringWord obj = ReverseStringWord();
	string text = "This is a simple words";
	cout << " Before Reverse : [" << text << "]";
	text = obj.reversing_word(text);
	cout << "\n After Reverse  : [" << text << "]";
	text = "It's to good ";
	cout << "\n Before Reverse : [" << text << "]";
	text = obj.reversing_word(text);
	cout << "\n After Reverse  : [" << text << "]";
	return 0;
}

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

//Include namespace system
using System;

// C# program
// Reverse individual words of the sentence

//Stack Node
class Node
{
	public char data;
	public Node next;
	public Node(char data)
	{
		this.data = data;
		this.next = null;
	}
}
//Define custom stack and its operation
class MyStack
{
	public Node top;
	public MyStack()
	{
		this.top = null;
	}
	//Add a new element in stack
	public void push(char data)
	{
		//Make a new stack node
		Node new_node = new Node(data);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			Console.Write("Memory overflow\n");
		}
	}
	//remove a top element in stack
	public void pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	//check that whether stack is empty or not
	public Boolean is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public char peek()
	{
		if (this.top != null)
		{
			return this.top.data;
		}
		else
		{
			return ' ';
		}
	}
}
class ReverseStringWord
{
	// Reverse the given string words
	public String reversing_word(String text)
	{
		int size = text.Length;
		//Auxiliary variable which is used to store result of string
		String result = "";
		//Create an stack
		MyStack stack = new MyStack();
		// Add element into stack
		for (int i = 0; i < size; i++)
		{
			if (text[i] == ' ')
			{
				// iterating the stack elements until if not empty
				while (stack.is_empty() == false)
				{
					//Get top element
					result += stack.peek();
					//remove current top
					stack.pop();
				}
				result += " ";
			}
			else
			{
				//Add element into stack
				stack.push(text[i]);
			}
		}
		// When last words are exist in stack
		while (stack.is_empty() == false)
		{
			//Get top element
			result += stack.peek();
			//remove current top
			stack.pop();
		}
		return result;
	}
	public static void Main(String[] args)
	{
		ReverseStringWord obj = new ReverseStringWord();
		String text = "This is a simple words";
		Console.Write(" Before Reverse : [" + text + "]");
		text = obj.reversing_word(text);
		Console.Write("\n After Reverse  : [" + text + "]");
		text = "It's to good ";
		Console.Write("\n Before Reverse : [" + text + "]");
		text = obj.reversing_word(text);
		Console.Write("\n After Reverse  : [" + text + "]");
	}
}

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

<?php
// Php program
// Reverse individual words of the sentence

//Stack Node
class Node
{
	public $data;
	public $next;

	function __construct($data)
	{
		$this->data = $data;
		$this->next = null;
	}
}
//Define custom stack and its operation
class MyStack
{
	public $top;

	function __construct()
	{
		$this->top = null;
	}
	//Add a new element in stack
	public	function push($data)
	{
		//Make a new stack node
		$new_node = new Node($data);
		if ($new_node != null)
		{
			$new_node->next = $this->top;
			$this->top = $new_node;
		}
		else
		{
			echo "Memory overflow\n";
		}
	}
	//remove a top element in stack
	public	function pop()
	{
		if ($this->top != null)
		{
			$this->top = $this->top->next;
		}
	}
	//check that whether stack is empty or not
	public	function is_empty()
	{
		if ($this->top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	public	function peek()
	{
		if ($this->top != null)
		{
			return $this->top->data;
		}
		else
		{
			return ' ';
		}
	}
}
class ReverseStringWord
{
	// Reverse the given string words
	public	function reversing_word($text)
	{
		$size = strlen($text);
		//Auxiliary variable which is used to store result of string
		$result = "";
		//Create an stack
		$stack = new MyStack();
		// Add element into stack
		for ($i = 0; $i < $size; $i++)
		{
			if ($text[$i] == ' ')
			{
				// iterating the stack elements until if not empty
				while ($stack->is_empty() == false)
				{
					//Get top element
					$result .= $stack->peek();
					//remove current top
					$stack->pop();
				}
				$result .= " ";
			}
			else
			{
				//Add element into stack
				$stack->push($text[$i]);
			}
		}
		// When last words are exist in stack
		while ($stack->is_empty() == false)
		{
			//Get top element
			$result .= $stack->peek();
			//remove current top
			$stack->pop();
		}
		return $result;
	}
}

function main()
{
	$obj = new ReverseStringWord();
	$text = "This is a simple words";
	echo " Before Reverse : [". $text ."]";
	$text = $obj->reversing_word($text);
	echo "\n After Reverse  : [". $text ."]";
	$text = "It's to good ";
	echo "\n Before Reverse : [". $text ."]";
	$text = $obj->reversing_word($text);
	echo "\n After Reverse  : [". $text ."]";
}
main();

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

// Node Js program
// Reverse individual words of the sentence

//Stack Node
class Node
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
//Define custom stack and its operation
class MyStack
{
	constructor()
	{
		this.top = null;
	}
	//Add a new element in stack
	push(data)
	{
		//Make a new stack node
		var new_node = new Node(data);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			process.stdout.write("Memory overflow\n");
		}
	}
	//remove a top element in stack
	pop()
	{
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	//check that whether stack is empty or not
	is_empty()
	{
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	peek()
	{
		if (this.top != null)
		{
			return this.top.data;
		}
		else
		{
			return ' ';
		}
	}
}
class ReverseStringWord
{
	// Reverse the given string words
	reversing_word(text)
	{
		var size = text.length;
		//Auxiliary variable which is used to store result of string
		var result = "";
		//Create an stack
		var stack = new MyStack();
		// Add element into stack
		for (var i = 0; i < size; i++)
		{
			if (text[i] == ' ')
			{
				// iterating the stack elements until if not empty
				while (stack.is_empty() == false)
				{
					//Get top element
					result += stack.peek();
					//remove current top
					stack.pop();
				}
				result += " ";
			}
			else
			{
				//Add element into stack
				stack.push(text[i]);
			}
		}
		// When last words are exist in stack
		while (stack.is_empty() == false)
		{
			//Get top element
			result += stack.peek();
			//remove current top
			stack.pop();
		}
		return result;
	}
}

function main()
{
	var obj = new ReverseStringWord();
	var text = "This is a simple words";
	process.stdout.write(" Before Reverse : [" + text + "]");
	text = obj.reversing_word(text);
	process.stdout.write("\n After Reverse  : [" + text + "]");
	text = "It's to good ";
	process.stdout.write("\n Before Reverse : [" + text + "]");
	text = obj.reversing_word(text);
	process.stdout.write("\n After Reverse  : [" + text + "]");
}
main();

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

#  Python 3 program
#  Reverse individual words of the sentence

# Stack Node
class Node :
	
	def __init__(self, data) :
		self.data = data
		self.next = None
	

# Define custom stack and its operation
class MyStack :
	
	def __init__(self) :
		self.top = None
	
	# Add a new element in stack
	def push(self, data) :
		# Make a new stack node
		new_node = Node(data)
		if (new_node != None) :
			new_node.next = self.top
			self.top = new_node
		else :
			print("Memory overflow\n", end = "")
		
	
	# remove a top element in stack
	def pop(self) :
		if (self.top != None) :
			self.top = self.top.next
		
	
	# check that whether stack is empty or not
	def is_empty(self) :
		if (self.top != None) :
			return False
		else :
			return True
		
	
	# Used to get top element of stack
	def peek(self) :
		if (self.top != None) :
			return self.top.data
		else :
			return ' '
		
	

class ReverseStringWord :
	#  Reverse the given string words
	def reversing_word(self, text) :
		size = len(text)
		# Auxiliary variable which is used to store result of string
		result = ""
		# Create an stack
		stack = MyStack()
		i = 0
		#  Add element into stack
		while (i < size) :
			if (text[i] == ' ') :
				#  iterating the stack elements until if not empty
				while (stack.is_empty() == False) :
					# Get top element
					result += stack.peek()
					# remove current top
					stack.pop()
				
				result += " "
			else :
				# Add element into stack
				stack.push(text[i])
			
			i += 1
		
		#  When last words are exist in stack
		while (stack.is_empty() == False) :
			# Get top element
			result += stack.peek()
			# remove current top
			stack.pop()
		
		return result
	

def main() :
	obj = ReverseStringWord()
	text = "This is a simple words"
	print(" Before Reverse : [{0}]".format(text), end = "")
	text = obj.reversing_word(text)
	print("\n After Reverse  : [{0}]".format(text), end = "")
	text = "It's to good "
	print("\n Before Reverse : [{0}]".format(text), end = "")
	text = obj.reversing_word(text)
	print("\n After Reverse  : [{0}]".format(text), end = "")

if __name__ == "__main__": main()

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

#  Ruby program
#  Reverse individual words of the sentence

# Stack Node
class Node  
	# Define the accessor and reader of class Node  
	attr_reader :data, :next
	attr_accessor :data, :next
 
	
	def initialize(data) 
		self.data = data
		self.next = nil
	end

end

# Define custom stack and its operation
class MyStack  
	# Define the accessor and reader of class MyStack  
	attr_reader :top
	attr_accessor :top
 
	
	def initialize() 
		self.top = nil
	end

	# Add a new element in stack
	def push(data) 
		# Make a new stack node
		new_node = Node.new(data)
		if (new_node != nil) 
			new_node.next = self.top
			self.top = new_node
		else 
			print("Memory overflow\n")
		end

	end

	# remove a top element in stack
	def pop() 
		if (self.top != nil) 
			self.top = self.top.next
		end

	end

	# check that whether stack is empty or not
	def is_empty() 
		if (self.top != nil) 
			return false
		else 
			return true
		end

	end

	# Used to get top element of stack
	def peek() 
		if (self.top != nil) 
			return self.top.data
		else 
			return ' '
		end

	end

end

class ReverseStringWord 
	#  Reverse the given string words
	def reversing_word(text) 
		size = text.length()
		# Auxiliary variable which is used to store result of string
		result = ""
		# Create an stack
		stack = MyStack.new()
		i = 0
		#  Add element into stack
		while (i < size) 
			if (text[i] == ' ') 
				#  iterating the stack elements until if not empty
				while (stack.is_empty() == false) 
					# Get top element
					result += stack.peek()
					# remove current top
					stack.pop()
				end

				result += " "
			else 
				# Add element into stack
				stack.push(text[i])
			end

			i += 1
		end

		#  When last words are exist in stack
		while (stack.is_empty() == false) 
			# Get top element
			result += stack.peek()
			# remove current top
			stack.pop()
		end

		return result
	end

end

def main() 
	obj = ReverseStringWord.new()
	text = "This is a simple words"
	print(" Before Reverse : [", text ,"]")
	text = obj.reversing_word(text)
	print("\n After Reverse  : [", text ,"]")
	text = "It's to good "
	print("\n Before Reverse : [", text ,"]")
	text = obj.reversing_word(text)
	print("\n After Reverse  : [", text ,"]")
end

main()

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

// Scala program
// Reverse individual words of the sentence

//Stack Node
class Node(var data: Character,
	var next: Node)
{
	def this(data: Char)
	{
		this(data, null);
	}
}
//Define custom stack and its operation
class MyStack(var top: Node)
{
	def this()
	{
		this(null);
	}
	//Add a new element in stack
	def push(data: Char): Unit = {
		//Make a new stack node
		var new_node: Node = new Node(data);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
		else
		{
			print("Memory overflow\n");
		}
	}
	//remove a top element in stack
	def pop(): Unit = {
		if (this.top != null)
		{
			this.top = this.top.next;
		}
	}
	//check that whether stack is empty or not
	def is_empty(): Boolean = {
		if (this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	def peek(): Char = {
		if (this.top != null)
		{
			return this.top.data;
		}
		else
		{
			return ' ';
		}
	}
}
class ReverseStringWord
{
	// Reverse the given string words
	def reversing_word(text: String): String = {
		var size: Int = text.length();
		//Auxiliary variable which is used to store result of string
		var result: String = "";
		//Create an stack
		var stack: MyStack = new MyStack();
		var i: Int = 0;
		// Add element into stack
		while (i < size)
		{
			if (text(i) == ' ')
			{
				// iterating the stack elements until if not empty
				while (stack.is_empty() == false)
				{
					//Get top element
					result += stack.peek();
					//remove current top
					stack.pop();
				}
				result += " ";
			}
			else
			{
				//Add element into stack
				stack.push(text(i));
			}
			i += 1;
		}
		// When last words are exist in stack
		while (stack.is_empty() == false)
		{
			//Get top element
			result += stack.peek();
			//remove current top
			stack.pop();
		}
		return result;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: ReverseStringWord = new ReverseStringWord();
		var text: String = "This is a simple words";
		print(" Before Reverse : [" + text + "]");
		text = obj.reversing_word(text);
		print("\n After Reverse  : [" + text + "]");
		text = "It's to good ";
		print("\n Before Reverse : [" + text + "]");
		text = obj.reversing_word(text);
		print("\n After Reverse  : [" + text + "]");
	}
}

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It's to good ]
 After Reverse  : [s'tI ot doog ]

// Swift 4 program
// Reverse individual words of the sentence

//Stack Node
class Node
{
	var data: Character;
	var next: Node? ;
	init(_ data: Character)
	{
		self.data = data;
		self.next = nil;
	}
}
//Define custom stack and its operation
class MyStack
{
	var top: Node? ;
	init()
	{
		self.top = nil;
	}
	//Add a new element in stack
	func push(_ data: Character)
	{
		//Make a new stack node
		let new_node: Node? = Node(data);
		if (new_node != nil)
		{
			new_node!.next = self.top;
			self.top = new_node;
		}
		else
		{
			print("Memory overflow\n", terminator: "");
		}
	}
	//remove a top element in stack
	func pop()
	{
		if (self.top != nil)
		{
			self.top = self.top!.next;
		}
	}
	//check that whether stack is empty or not
	func is_empty() -> Bool
	{
		if (self.top != nil)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//Used to get top element of stack
	func peek() -> Character
	{
		if (self.top != nil)
		{
			return self.top!.data;
		}
		else
		{
			return " ";
		}
	}
}
class ReverseStringWord
{
	// Reverse the given string words
	func reversing_word(_ text: String) -> String
	{
		let size: Int = text.count;
		//Auxiliary variable which is used to store result of string
		var result: String = "";
		//Create an stack
		let stack: MyStack = MyStack();
		var i: Int = 0;
      	var data : Character;
		// Add element into stack
		while (i < size)
		{
            data = Array(text)[i];
			if (data == " ")
			{
				// iterating the stack elements until if not empty
				while (stack.is_empty() == false)
				{
					//Get top element
					result +=  String(stack.peek());
					//remove current top
					stack.pop();
				}
				result += " ";
			}
			else
			{
				//Add element into stack
				stack.push(data);
			}
			i += 1;
		}
		// When last words are exist in stack
		while (stack.is_empty() == false)
		{
			//Get top element
			result += String(stack.peek());
			//remove current top
			stack.pop();
		}
		return result;
	}
}
func main()
{
	let obj: ReverseStringWord = ReverseStringWord();
	var text: String = "This is a simple words";
	print(" Before Reverse : [\(text)]", terminator: "");
	text = obj.reversing_word(text);
	print("\n After Reverse  : [\(text)]", terminator: "");
	text = "It\"s to good ";
	print("\n Before Reverse : [\(text)]", terminator: "");
	text = obj.reversing_word(text);
	print("\n After Reverse  : [\(text)]", terminator: "");
}
main();

 Before Reverse : [This is a simple words]
 After Reverse  : [sihT si a elpmis sdrow]
 Before Reverse : [It"s to good ]
 After Reverse  : [s"tI ot doog ]

Time Complexity Analysis

Let n be the length of the input string. The time complexity of the algorithm is O(n) because we iterate through the input string once and perform constant-time operations for each character (push, pop, append to the result string). Therefore, the overall time complexity is linear, O(n).

Output Explanation

The output shows the original string and the string with individual words reversed. For example, "Before Reverse : [This is a simple words]" and "After Reverse : [sihT si a elpmis sdrow]" represent the input string "This is a simple words" and the output string after reversing individual words, respectively.