Reverse words of a sentence without using String.Split in C#

Question

Recently I have been asked in a discussion to write an algorithm to implement reverse of words of a sentence (Not reverse of whole sentence) without using string operations such as Split/Replace/Reverse/Join except ToCharArray and Length. The below is what I could devise in 5min of time. Though the algorithm is working fine, it seems bit ugly style of implementation. Can some body help me by polishing the code.

string ReverseWords(string s)
{
    string reverseString = string.Empty;
    string word = string.Empty;

    var chars = s.ToCharArray();
    List<ArrayList> words = new List<ArrayList>();
    ArrayList addedChars = new ArrayList();
    Char[] reversedChars = new Char[chars.Length];
    int i = 1;
    foreach (char c in chars)
    {
        if (c != ' ')
        {
            addedChars.Add(c);
        }
        else
        {
            words.Add(new ArrayList(addedChars));
            addedChars.Clear();
        }
        if (i == s.Length)
        {
            words.Add(new ArrayList(addedChars));
            addedChars.Clear();
        }
        i++;
    }
    foreach (ArrayList a in words)
    {
        for (int counter = a.Count - 1; counter >= 0; counter--)
        {
            reverseString += a[counter];
        }
        if(reverseString.Length < s.Length)
            reverseString += " ";
    }
    return reverseString;
}

Well if you avoid `Split/Replace/Reverse/Join ...` it is gonna be a bit ugly ! ! — V4Vendetta, Dec 24 '12 at 06:34
`Reverse` is an extension method of `IEnumerable`, not a string method. — Asad Saeeduddin, Aug 23 '16 at 21:36

score 8 · Answer 1 · answered Dec 24 '12 at 06:46

8

There is a relatively elegant solution which uses a LIFO stack.
Question however sounds like homework, so I'll only provide the pseudo code.

currWord = new LIFO stack of characters
while (! end of string/array)
{
  c = next character in string/array
  if (c == some_white_space_character) {
     while (currWord not empty) {
       c2 = currWord.pop()
       print(c2)
     }
     print(c)
  }
  else
    currWord.push(c)
}

answered Dec 24 '12 at 06:46

mjv

73,152
14
113
156

@StanR. I believe you are correct. Interesting concept though. – John Davis Jun 29 '13 at 23:38

score 6 · Accepted Answer · answered Dec 24 '12 at 06:59

6

This is somewhat simpler:

string inp = "hai how are you?";
StringBuilder strb = new StringBuilder();
List<char> charlist = new List<char>();
for (int c = 0; c < inp.Length; c++ )
{

    if (inp[c] == ' ' || c == inp.Length - 1)
    {
        if (c == inp.Length - 1)
            charlist.Add(inp[c]);
        for (int i = charlist.Count - 1; i >= 0; i--)
            strb.Append(charlist[i]);

        strb.Append(' ');
        charlist = new List<char>();
    }
    else
        charlist.Add(inp[c]);
}
string output = strb.ToString();

answered Dec 24 '12 at 06:59

Uthistran Selvaraj

1,371
1
12
31

This is what the polished version of the above algorithm which I have asked for. Thanks kovilpatti C sharper – gee'K'iran Dec 24 '12 at 07:16
Here is the another BEST solution -> http://stackoverflow.com/questions/1009160/reverse-the-ordering-of-words-in-a-string – sandeep talabathula Aug 02 '13 at 15:53

score 2 · Answer 3 · answered Dec 24 '12 at 17:43

Kind of a polished version:-

string words = "hi! how are you!";
string reversedWords = "";

List<int> spaceEncounter = new List<int>();
spaceEncounter.Add(words.Length - 1);

for (int i = words.Length - 1; i > 0; i--)
{ 
    if(words[i].Equals(' '))
    {
        spaceEncounter.Add(i);

        for (int j = i+1; j < spaceEncounter[spaceEncounter.Count - 2]; j++)
            reversedWords += words[j];

        reversedWords += " ";
    }
}

for (int i = 0; i < spaceEncounter[spaceEncounter.Count - 1]; i++)
    reversedWords += words[i];

Nice Example for reverse the sentences. Thanks – vipin katiyar Jul 15 '13 at 06:22 — vipin katiyar, Jul 15 '13 at 06:22

score 1 · Answer 4 · edited Jun 29 '13 at 23:26

1

There is a small bug in your code. Due to this, the output string would be displayed as yo are how hi!, given the input string hi! how are you. It's truncating the last char of the last word.

Change this:

spaceEncounter.Add(words.Length - 1);

To:

spaceEncounter.Add(words.Length);

edited Jun 29 '13 at 23:26

Danny Beckett

20,529
24
107
134

answered Jun 29 '13 at 23:04

Sushant

11
1

Asad Saeeduddin · Answer 5 · 2016-08-23T22:50:11.937

1

Well, you didn't say anything about the other LINQ extension methods :)

static string ReverseWordsWithoutSplit(string input)
{
    var n = 0;
    var words = input.GroupBy(curr => curr == ' ' ? n++ : n);

    return words.Reverse().Aggregate("", (total, curr) => total + string.Concat(curr.TakeWhile(c => c != ' ')) + ' ');
}

edited Aug 23 '16 at 22:50

answered Aug 23 '16 at 22:38

Asad Saeeduddin

46,193
6
90
139

:-) Condition is that I shouldn't use framework features such as linq. Thanks for the answer though. It's clean and nice. – gee'K'iran Oct 24 '16 at 14:24

score 1 · Answer 6 · answered Mar 01 '18 at 11:57

One of the Easiest Answer is as given Below please go through it,

public static string ReversewordString(string Name)
    {
        string output="";
        char[] str = Name.ToCharArray();
        for (int i = str.Length - 1; i >= 0; i--)
        {
            if (str[i] == ' ')
            {
                output = output + " ";
                for (int j = i + 1; j < str.Length; j++)
                {
                    if (str[j] == ' ')
                    {
                        break;
                    }
                    output=output+ str[j];
                }
            }
            if (i == 0)
            {
                output = output +" ";
                int k = 0;
                do
                {
                    output = output + str[k];
                    k++;
                } while (str[k] != ' ');
            }
        }
        return output;
    }

score 0 · Answer 7 · answered Feb 01 '16 at 00:11

        string temp = string.Empty;
        string reversedString = string.Empty;

        foreach (var currentCharacter in testSentence)
        {
            if (currentCharacter != ' ')
            {
                temp = temp + currentCharacter;
            }
            else
            {
                reversedString = temp + " " + reversedString;
                temp = string.Empty;
            }
        }
        reversedString = temp + " " + reversedString;

score 0 · Answer 8 · answered Aug 23 '16 at 21:21

This version works in-place, without any intermediate data structures. First, it reverses the characters in each word. "me too" => "em oot". Then it reverses the whole string: "em oot" => "too me".

    public static string ReverseWords(string s)
    {
        if (string.IsNullOrEmpty(s))
            return s;

        char[] chars = s.ToCharArray();
        int wordStartIndex = -1;

        for (int i = 0; i < chars.Length; i++)
        {
            if (!Char.IsWhiteSpace(chars[i]) && wordStartIndex < 0)
            {
                // Remember word start index
                wordStartIndex = i;
            }
            else
            if (wordStartIndex >= 0 && (i == chars.Length-1 || Char.IsWhiteSpace(chars[i + 1]))) {
                // End of word detected, reverse the chacacters in the word range
                ReverseRange(chars, wordStartIndex, i);

                // The current word is complete, reset the start index  
                wordStartIndex = -1;
            }
        }

        // Reverse all chars in the string
        ReverseRange(chars, 0, chars.Length - 1);

        return new string(chars);
    }

    // Helper
    private static void ReverseRange(char[] chars, int startIndex, int endIndex)
    {
        for(int i = 0; i <= (endIndex - startIndex) / 2; i++)
        {
            char tmp = chars[startIndex + i];
            chars[startIndex + i] = chars[endIndex - i];
            chars[endIndex - i] = tmp;
        }            
    }

Hi there, i know this is an old question but i have been looking for an in place algorithm for the above question. Your solution is the one that closely mimicks mine. I want to know if you have any references that can substantiate your claim that this is indeed in place? It definitely agrees with my understanding of in place but i am concerned at our use of temp variables which, to be fair, are also using memory... — prismeyez83, Jul 15 '19 at 08:44

Sakhile Vinny Daweti · Answer 9 · 2017-11-29T12:35:56.020

0

How about a simple recursive function that checks for a " " and then substring accordingly?

    private static string rev(string inSent) { 
        if(inSent.IndexOf(" ") != -1) 
        { 
            int space = inSent.IndexOf(" "); 
            System.Text.StringBuilder st = new System.Text.StringBuilder(inSent.Substring(space+1)); 
            return rev(st.ToString()) + " " + inSent.Substring(0, space); 
        } 
        else 
        { 
            return inSent; 
        } 
    }

edited Nov 29 '17 at 12:35

answered Nov 28 '17 at 11:06

Sakhile Vinny Daweti

1
1
4

This is Java not C# ! – Mustapha Belmokhtar Nov 28 '17 at 11:17
Either way, logic... Now spot the difference and be sure to use System.Text. – Sakhile Vinny Daweti Nov 29 '17 at 12:24

score 0 · Answer 10 · answered Jul 31 '18 at 09:24

use stack in C#

string str = "ABCDEFG";
Stack<char> stack=new Stack<char>();
foreach (var c in str)
{
    stack.Push(c);
}
char[] chars=new char[stack.Count];
for (int i = 0; i < chars.Length; i++)
{
    chars[i]=stack.Pop();
}
var result=new string(chars); //GFEDCBA

Reverse words of a sentence without using String.Split in C#

10 Answers10

Linked