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
- Define a custom stack data structure with push, pop, is_empty, and peek operations.
- Create a function
reversing_word
that takes the input string as input and returns the string with individual words reversed. - Initialize an empty result string to store the final output.
- Iterate through the input string character by character.
- If the character is not a space, push it into the stack.
- 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.
- Continue the iteration until the end of the input string is reached.
- 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 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 + "]");
}
}
Output
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;
}
Output
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 + "]");
}
}
Output
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();
Output
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();
Output
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()
Output
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()
Output
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 + "]");
}
}
Output
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();
Output
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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment