Posts Reverse Words (geeksforgeeks - SDE Sheet)
Post
Cancel

Reverse Words (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

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

geeksforgeeks

SOLUTION

APPROACH 1 (TWO POINTERS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{

    String reverseWords(String s)
    {
        int n = s.length();

        // StringBuffer to store the reversed words
        StringBuffer sb = new StringBuffer();

        int i = n - 1; // Start from the end of the string
        int j = n - 1; // 'j' will mark the end of the current word while traversing from right to left

        // Traverse the string from the end to the beginning
        while(i >= 0)
        {
            // Move 'i' backwards to find the beginning of a word or the start of the string
            while(i >= 0 && s.charAt(i) != '.')
            {
                i--;
            }

            // Add the current word to the StringBuffer
            for(int k = i + 1; k <= j; k++)
            {
                sb.append(String.valueOf(s.charAt(k)));
            }

            // Move 'i' one step left to skip the dot
            // j will also move to the same position
            i--;
            j = i;

            sb.append(".");
        }

        // Remove the last dot that was added after the last word and return the result
        return sb.toString().substring(0, n);
    }
}

APPROACH 2 (APPEND TO LEFT)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution
{
    String reverseWords(String s)
    {
        int n = s.length();

        // res: store the final result
        // current: accumulate characters of the current word
        String res = "";
        String current = "";

        for(int i = 0; i < n; i++)
        {
            char ch = s.charAt(i);

            // Check if the current character is a dot, indicating the end of a word.
            if(ch == '.')
            {
                // Prepend the current word and dot to 'res'.
                res = "." + current + res;

                // Reset 'current' to start accumulating the next word.
                current = "";
            }
            else
            {
                // If it's not a dot, add the character to 'current' to form the current word.
                current += ch;
            }
        }

        // After the loop, 'current' contains the last word. Add it to 'res' without a preceding dot.
        res = current + res;

        return res;
    }
}
This post is licensed under CC BY 4.0 by the author.