Skip to main content

Reverse words in a given string

Question: Given a String S, reverse the string without reversing its individual words. Words are separated by dots.

Example 1:

Input:
S = i.like.this.program.very.much
Output: much.very.program.this.like.i
Explanation: After reversing the whole
string(not individual words), the input
string becomes
much.very.program.this.like.i

Solution 1: Brute Force
Split the string with dots and store each word in any array. Iterate the words array in reverse and append each word in the string followed by a space as seprartor.
Assumption here is that there is single dot separating the words.

Input:


class Solution {
    String reverseWords(String S) {
       final String[] arr =  S.split("\\.");
       String output = "";
       final int len = arr.length;
       if (len == 1) {
           return arr[0];
       } else if (len == 0) {
           return output;
       } else {
           for (int i = len - 1; i > 0; i--) {
               output = output + arr[i] + ".";
           }
           output = output + arr[0]
           return output;
           
       }
    }
}
Complexity of the solution is O(n) because the split function iterates the whole string to find the dot.



Comments

Post a Comment

Popular posts from this blog

A Very Basic yet important question in a life of a software developer

 Processes Vs Threads Process:  It is an execution unit where a program runs. The OS helps to create, schedule, and terminates the processes which is used by CPU. The other processes created by the main process are called child process. A process operations can be controlled with the help of PCB(Process Control Block). PCB contains all the crucial information related to processing like process id, priority, state, and contents CPU register, etc. Important properties of the process: - Creation of each process requires separate system calls for each process. - It is an isolated execution entity and does not share data and information. - Processes use the IPC(Inter-Process Communication) mechanism for communication that significantly increases the number of system calls. - Process management takes more system calls. - A process has its stack, heap memory, and data map. Thread:   A process can have multiple threads, all executing at the same time. A thread is lightw...
Post a Comment
Read more

Count the Reversals

Problem Statement: Given a string  S  consisting only of opening and closing curly brackets  '{'  and  '}'  find out the minimum number of reversals required to make a balanced expression. Input The first line of input contains an integer  T  denoting the number of test cases. Then  T  test cases follow.  The first line of each test case contains a string  S  consisting only of  {  and  } . Output Print out minimum reversals required to make  S  balanced.If it cannot be balanced, then print  -1 . Constraints 1 <=  T  <= 100 0 <    S   <= 50 Examples   Input 4 }{{}}{{{ {{}}}} {{}{{{}{{}}{{ {{{{}}}} Output 3 1 -1 0 Expected Complexity Time :   O(n) Space : O(n) Code: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { Scanner sc=new Scanner(S...
Post a Comment
Read more

CheatSheet for Searching Algorithms

CheatSheet for Searching Algorithms 1. Linear Search int search(int arr[], int x) { int n = arr.length; for(int i = 0; i < n; i++) { if(arr[i] == x) return i; } return -1; } The time complexity of above algorithm is O(n). 2. Binary Search // Returns location of key, or -1 if not found // Returns location of key, or -1 if not found int BinarySearch(int A[], int l, int r, int key) { int m; while( l <= r ) { m = l + (r-l)/2; if( A[m] == key ) // first comparison return m; if( A[m] < key ) // second comparison l = m + 1; else r = m - 1; } return -1; } The time complexity of Binary Search Theta(log(n)) Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space. 3. The Ubiquitous Binary Search // Invariant: A[l] <= key and A[r] > key // Boundar...
Post a Comment
Read more