Reversing a string with constrained requirements

Question

I just started learning C# and I need some help. I have to reverse a string and check for palindrome using ONLY if, else, switch, s.Length, s.Substring and s[]:

    static string MyReverseString(string s)
    {
        int len = s.Length;
        string NewS= "";
        if (len != 0)
        {
            NewS = NewS + s[len];

            return MyReverseString(s.Substring(0, (len - 1)));
        }
        else
        {
            return NewS;

        }
    }

and I get

"Index was outside the bounds of the array."

Like I mentioned in the post, I can not use other than if, else, Switch, s.Length, s.Substring and s[]. — TesterTemp, Nov 18 '17 at 23:17
Whats wring with looping backwards thru the string to assign the chars to a new string? — Ňɏssa Pøngjǣrdenlarp, Nov 18 '17 at 23:19
@Stijn I already tried " int len = s.Length - 1 ; " and "if(len > 0) " and still didn't work. Thank you for your comment but i can search by myself. — TesterTemp, Nov 18 '17 at 23:28
I suggest you take your time and properly read the duplicate. Then you'll understand why your code doesn't work, and why your other attempt with `- 1` doesn't work either. — user247702, Nov 18 '17 at 23:31

InBetween · Accepted Answer · 2017-11-18T23:46:37.467

Your general idea is correct, but you are not quite there.

When using recursion, code first the case where recursion isn't needed. When reversing a string, what is the trivial case? Well, when the string is empty or is only one character long. Ok, lets do that:

public static string Reverse(string s)
{
    if (s.Length <= 1)
        return s;

    //do something else
}

Ok, now, if s isn't empty, how do we reverse recursively? Well, let's think about what should be returned in the current step. Obviously, if we want to reverse s, whatever we return, we know that the first letter needs to be the last letter of s. Ok, lets do that and see where it takes us:

public static string Reverse(string s)
{
    if (s.Length <= 1)
        return s;

    return s[s.Length - 1] + //something
}

And what is that something? Well it has to be the reverse of s without the last letter, we already took care of that one, remember? But... oh wait! I know how to reverse a string already, don't I? Reverse(s.Substring(0, s.Length - 1) (isn't recursion magical?)

Et violá:

public static string Reverse(string s)
{
    if (s.Length <= 1)
        return s;

    return s[s.Length - 1] + Reverse(s.Substring(0, s.Length - 1));
}

You didn't even need switch and else.

Trivial case condition can be slightly optimised to `s.Length <= 1` (single-character string does not need to be reversed) and `Reverse(` is missing closing parenthesis. — Ňuf, Nov 18 '17 at 23:41

score 0 · Answer 2 · answered Nov 18 '17 at 23:29

Here, s[len] is throwing an IndexOutOfRange exception. Lets say - If you have string s = "abc" then index start from 0. So s[2] would be "c" and length of string is 3. So, if you try to get s[len] which is s[3], it will throw an exception.

Check it out - Best way to reverse a string

A. Milto · Answer 3 · 2017-11-18T23:50:11.553

To reverse the string you cut it in half, swap the halves and reverse them recursively in this manner until they are the size of 1 or 0 characters.

To check for palindrome you check if the first and the last character are the same. If that is not true, the string is definitely not a palindrome. If true, then check if the smaller part of the original string (besides the first and the last character) is a palindrome recursively in the same way.

    static string Reverse(string s)
    {
        if (s.Length >= 2)
            return Reverse(s.Substring(s.Length / 2)) + Reverse(s.Substring(0, s.Length / 2));
        else
            return s;
    }

    static bool IsPalindrome(string s)
    {
        if (s.Length <= 1)
            return true;

        if (s[0] == s[s.Length - 1] && IsPalindrome(s.Substring(1, s.Length-2)))
            return true;
        else
            return false;
    }

score 0 · Answer 4 · answered Nov 19 '17 at 00:00

Try this:

public static string MyReverseString(string s)
{
    return MyReverseString(s, s.Length - 1);
}

private static string MyReverseString(string s, int index)
{
    if (index > 0)
    {
        return s[index] + MyReverseString(s, index - 1);
    }
    else
    {
        return s[index].ToString();
    }
}

This avoids using .Substring (which improves efficiency slightly).

If you want to find a palindrome and you don't care about reversing the string, then try this:

public static bool IsPalindrome(string s)
{
    return IsPalindrome(s, 0, s.Length - 1);
}

private static bool IsPalindrome(string s, int start, int finish)
{
    if (finish - start <= 0)
    {
        return true;
    }
    else
    {
        if (s[start] != s[finish])
        {
            return false;
        }
        else
        {
            return IsPalindrome(s, start + 1, finish - 1);
        }
    }
}

This final method can be shortened to:

private static bool IsPalindrome(string s, int start, int finish)
{
    return (finish - start <= 0) || (s[start] == s[finish]) && IsPalindrome(s, start + 1, finish - 1);
}

Reversing a string with constrained requirements

4 Answers4