6
\$\begingroup\$

The Challenge: Given a string, return a string where each word is reversed individually without changing its position. EDIT: (i.e.: the input "hello world I am a frog?" should produce the output: "olleh dlrow I ma a gorf?")

Thoughts and questions: Perhaps I was cheating the spirit of the challenge by using string builder? What do you think?

Complexity? Would the complexity be? I feel like it is O(n) since it will basically look at almost every char twice. I'm thinking there is a more efficient way to do it where n is just looked at once, but I think that to achieve that we will double the use of memory. Not that that is a problem, but I think that is the trade off.

Coding tests tend to be timed and I did this quickly. In evaluating the code, how do you factor in the pressure of time as you administer the test? I am talking myself into the idea that the answer should have been creating a new string and entering the chars one at a time using pointers so that each string char is looked at once and moved once. Is that really better then this solution? Perhaps there are points for easily readable code? Do you think this is readable?

    public static string ReverseOnlyWords(string InitialValue)
    {
        if (InitialValue == null)
        {
            throw new System.NullReferenceException();
        }
        StringBuilder seperatedValue = new StringBuilder();
        StringBuilder currentWord = new StringBuilder();
        foreach (char c in InitialValue)
        {
            if (c == ' ' || c == '.' || c == ',')
            {
                seperatedValue.Append(Reverse(currentWord.ToString()));
                seperatedValue.Append(c.ToString());
                currentWord.Clear();
            }
            else
            {
                currentWord.Append(c.ToString());
            }
        }
        seperatedValue.Append(Reverse(currentWord.ToString()));

        string resultValue = seperatedValue.ToString();
        return resultValue;
    }

In Reverse, perhaps I should have simply created a copy of toBeReversed and inserted/replaced characters in the reversed order instead of a string builder?

    static public string Reverse(string toBeReversed)
    {
        if (toBeReversed == null)
        {
            throw new System.NullReferenceException();
        }
        StringBuilder reversedString = new StringBuilder();
        for (int i = (toBeReversed.Length - 1); i >= 0; i--)
        {
            reversedString.Append(toBeReversed[i].ToString());
        }
        return reversedString.ToString();
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ Small note: throw System.ArgumentNullException, not System.NullReferenceException. \$\endgroup\$ – Jesse C. Slicer Aug 7 '20 at 20:30
  • 1
    \$\begingroup\$ Using StringBuilder is OK. \$\endgroup\$ – Alexander Petrov Aug 7 '20 at 23:23
  • 4
    \$\begingroup\$ Note on the reverse. Usually, no one ever considers that a string may contain Unicode surrogate pairs. Simply copying one char at a time will result in incorrect results. \$\endgroup\$ – Alexander Petrov Aug 7 '20 at 23:25
  • 4
    \$\begingroup\$ Other note. The string can be a combination of Unicode characters. Accent, umlaut, etc. Again, copying one character at a time will lead to a strange result when, for example, the accent is on a consonant letter. \$\endgroup\$ – Alexander Petrov Aug 7 '20 at 23:28
  • 1
    \$\begingroup\$ How is the string "That's well-known" supposed to be reversed? Or, in other words, what exactly is "a word"? I'd like it if the capitalization of the words were preserved, but that's just not mentioned in the original task. \$\endgroup\$ – Roland Illig Aug 11 '20 at 4:54
4
\$\begingroup\$

First, NullReferenceException is used by the CLR, and it's the default exception for nullity in most cases. The ArgumentNullException used to prevent NullReferenceException from thrown, and gives more meaningful exception to your code.

So, in your current code, if you pass a null, the thrown exception message would be something like

Object reference not set to an instance of an object

. This would not give you any hint on what's going on your code, so if you used

throw new ArgumentNullException(nameof(InitialValue));

this would give you something like :

Value cannot be null. (Parameter 'InitialValue')   

isn't clearer to point out the issue ?

Another point is that you don't need to throw an exception all the time as a way to handle your code. Only throw exception when it's critical to the application. As exceptions like a Stop sign to the application, whenever it's thrown, it stops the application from running the code. if the code is related to other dependencies such as required class, extensions, databases, ..etc. Then, this code should throw an exception if it leaks the dependency requirements.

In your case, it's not critical to pass null, yes it would break the code, but also it's not required to stop the code just for this, as you can simply return null to the caller. Same thing if Empty string or Whitespace passed. because you

so if you do this :

if(string.IsNullOrWhitespace(value)) { return value; }

would be enough and better than thrown exception for this case.

For the methods ReverseOnlyWords and Reverse I don't see what was the reason behind splitting them?. It should be one method that does the process. having two methods is confusing, because it's required to us (or any developer) to read both methods to understand the logic and to know which to use ! of course, splitting methods can be useful if there are independent procedures inside the method that can be reused or simply outside the main scope of the method, but not in your current code.

Using StringBuilder is a good practice. However, you only need one, the other one is unnecessary. Also, you don't need ToString() when appending char in StringBuilder

this line :

if (c == ' ' || c == '.' || c == ',') { ... }

punctuations can't be handled like this, because if you keep it that way, you will miss other punctuations. if we assumed you'll process English context, then you only covered 3 out of 14 punctuations that I know of. What about other languages? So Instead, use the built in char.IsPunctuation which covers most of the punctuations that in UnicodeCategory.

Complexity? Would the complexity be? I feel like it is O(n) since it will basically look at almost every char twice.

You're using 3 loops, so your complexity is \$O(N^2)\$. though, it can be simplified to two loops (one for the words, the other for the characters), and one StringBuilder is enough. However, the overall code can be written as follow :

public string Reverse(string value, char separator)
{       
    if(string.IsNullOrEmpty(value)) { return value; } // just return the value, leave the handling to the caller.
    
    var words = value.Split(separator); // split it to words by spaces

    // initiate a string builder with a fixed size based on the original string size. 
    // setting the capacity would avoid oversized allocation.
    var resultBuilder = new StringBuilder(value.Length);

    // iterate over words 
    for(int x=0; x < words.Length; x++)
    {           
        // store the tailing punctuation
        char? punctuation = null;
        // iterate over characters in reverse 
        for(int c = words[x].Length - 1; c >= 0; c--)
        {    
            var current = words[x][c];
        
            if(char.IsPunctuation(current))
            {
                if(c == 0) // for leading punctuation
                {
                    // get the first poistion of the current word 
                    var index = resultBuilder.ToString().Length - (words[x].Length - 1);
                    
                    // insert the leading punctuation to the first poition (its correct poistion)
                    resultBuilder.Insert(index, current);                     
                }
                else 
                {
                    // store tailing punctuation to insert it afterward
                    punctuation = current;
                }
                
            }
            else 
            {
                // everything else, just append
                resultBuilder.Append(current);                
            }                                
            
      }
        
        if(punctuation != null)
        {
            // insert tailing punctuation 
            resultBuilder.Append(punctuation);
            punctuation = null; //reset 
        }

        resultBuilder.Append(separator);        
    }

    return resultBuilder.ToString();
}           

this is just a revision of your code in its simplest form possible (at least to my knowledge) and it's one way process (process each word and character once). Using pointers would not increase the overall performance to the point where it would be recommended!. Array.Reverse also can be used, but still might add more memory allocation and slow down the performance specially with large strings.

Other missing part that needs to be counted when dealing with strings is Unicode which in some cases invalidate the results if not handled correctly.

UPDATE :

Here is another version that uses one loop, and two StringBuilder (one stores the results, and one for the processing).

public static string ReverseString(string value , char separator)
{
    if(string.IsNullOrEmpty(value)) { return value; }

    var tempBuilder = new StringBuilder(value.Length);

    var resultBuilder = new StringBuilder(value.Length);

    var isCompleted = false;

    for(int x = 0, index = value.Length - 1; index >= 0; index--, x++)
    {
        var current = value[index];
        
        if(current == separator)
        {
            isCompleted = true;
        }
        else
        {
            tempBuilder.Append(current);

            if(index == 0)
            {
                isCompleted = true;
            }
        }

        if(isCompleted)
        {
            // handle the lead and tail punctuations
            if(char.IsPunctuation(tempBuilder[0]) && char.IsPunctuation(tempBuilder[tempBuilder.Length - 1]))
            {
                var tail = tempBuilder[0];
                var lead = tempBuilder[tempBuilder.Length - 1];
                tempBuilder.Remove(0 , 1);
                tempBuilder.Remove(tempBuilder.Length - 1 , 1);
                tempBuilder.Insert(0 , lead);
                tempBuilder.Append(tail);
            }
            else if(char.IsPunctuation(tempBuilder[0]))
            {
                tempBuilder.Append(tempBuilder[0]);
                tempBuilder.Remove(0 , 1);
            }
            else if(char.IsPunctuation(tempBuilder[tempBuilder.Length - 1]))
            {
                tempBuilder.Insert(0 , tempBuilder[0]);
                tempBuilder.Remove(tempBuilder.Length - 1 , 1);
            }

            //store the results
            resultBuilder.Insert(0 , separator);
            resultBuilder.Insert(0 , tempBuilder);

            //reset
            tempBuilder.Clear();
            x = 0;
            isCompleted = false;

        }
    }

    return resultBuilder.ToString();
}

it may need more work, but I thought it would be useful to share it. It still lakes the Unicode handling though.

\$\endgroup\$
  • \$\begingroup\$ I had the reverse method at the start of coding. I was applying DRY, where I was using that method for others. and well also saving the time it took to code it. I do see that including it all in a single method could increase efficiency/speed and allow improvement to the algorithm. \$\endgroup\$ – amalgamate Aug 9 '20 at 16:50
  • 1
    \$\begingroup\$ I don't think the original is \$O(N^2)\$. It would require running through the string for each character in the string. A simple test indicates it is scaling linearly. \$\endgroup\$ – Johnbot Aug 10 '20 at 13:56
  • \$\begingroup\$ Thank you @Johnbot, I agree. In fairness, iSR5 does have the fastest algorithm. I played with mine to get closer to iSR5's and managed to match+ the speed by removing the use of a second string builder. The change of incorporating the method made no discernable difference in the timing. \$\endgroup\$ – amalgamate Aug 10 '20 at 16:26
  • \$\begingroup\$ @amalgamate check the updated version. I believe it's possible to use one StringBuilder to the updated version though. But it would add more handling , which adds more work ;). \$\endgroup\$ – iSR5 Aug 11 '20 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.