String reverse and pairing reversed words

These are questions from an interview:

• Reverse a string

• Find matching anagrams in a word list

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
public class ReverseString
{
    public ReverseString()
    {
        string str = "Gilad";
        string res = Reverse(str);

        List wordsList = new List();
        wordsList.Add("batel");            
        wordsList.Add("Gilad");
        wordsList.Add("daliG");
        wordsList.Add("enon");
        wordsList.Add("none");
        wordsList.Add("letab");
        var pairs = PairAnagramWords(wordsList);
    }

    public string Reverse(string str)
    {
        StringBuilder s = new StringBuilder();
        for (int i = str.Length - 1; i >= 0; i--)
        { 
            s.Append(str[i]);
        }
        return s.ToString();
    }

    Dictionary PairAnagramWords(List wordsList)
    {
        wordsList.Sort();
        Dictionary res = new Dictionary();
        foreach (var item in wordsList)
        {
            if (res.ContainsValue(item))
            {
                continue;
            }

            foreach (var item2 in wordsList)
            {
                if (item == item2 || item.Length != item2.Length)
                {
                    continue;
                }
                var reversed = Reverse(item2);
                int i;
                for (i = 0; i < item.Length; i++)
                {
                    if (item[i] != reversed[i])
                    {
                        break;
                    }
                }
                if (i == item.Length)
                {
                    res.Add(item, item2);
                }
            }
        }
        return res;
    }
}

}

I don't like the fact that I'm doing it in \$ O(n^2) \$, although I am checking for no repetitions.

Please review my code's complexity and algorithm. I did the testing inside the

Reverse

Your Reverse function is functional, but there are some improvements I could suggest:

• if you use the StringBuilder approach (which is OK), then you should at least initialize the size of the internal capacity so that resizes are not needed later (for performance reasons). Use StringBuilder s = new StringBuilder(str.Length);

• While looking at that, why have the variable name s ... that's a poor choice.

• Consider using a char[] array for the reverse as it reduces some more overheads (again, performance). StringBuilders are useful for many things, but their biggest benefit comes from their dynamic nature. In this case, that nature is not needed.

If it was me, I would have:

public string Reverse(string forward)
    {
        char[] chars = forward.ToCharArray();
        var last = forward.Length - 1;
        for (int i = last / 2; i >= 0; i--)
        { 
            char temp = chars[i];
            chars[i] = chars[last - i];
            chars[last - i] = temp;
        }
        return new String(chars);
    }

Matching Anagrams

Your code is not matching anagrams. Your code matches words with the reverse of the word. An anagram is any rearranged form of the word. So, you have batel and lateb in your list, but it should also match table. Your code will not do that.

The trick to solving this problem would be to reduce each word to its sorted array of characters. For example, to have a function like:

public string SortedString(string word)
    {
        char[] chars = word.ToCharArray();
        Array.Sort(chars);
        return new String(chars);
    }

Or, if Linq is your thing:

return String.Concat(word.OrderBy(c => c));

With the char-sorted words, you can use the sorted version as the key of a dictionary, something like:

Dictionary> anagrams = ....

And you can then populate that dictionary with lists of words that have the same sorted-char anagram key.

Once you have that, you can return all words that are anagrams of each other.

StackExchange Code Review Q#73561, answer score: 4