Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Ask someone's help to explain the performance issue of C# code

I am a C# developer and I am training my coding and algorithm skills on LeetCode.
And now I am handling the problem 5: longest palindromic substring.
I want someone can explain the reason.
My solution version 1 to this problem was:

public string LongestPalindrome(string s)
{
    // Step 0: Handles invalid or special cases.
    if (string.IsNullOrWhiteSpace(s) ||
        s.Length == 1 ||
        s.Distinct().Count() == 1 ||
        s.Reverse().SequenceEqual(s))
        {
            return s;
        }

        if (s.Length == 2)
        {
            return s.First().Equals(s.Last()) ? s : s.First().ToString();
        }

        if (s.Distinct().Count() == s.Length)
        {
            return s.First().ToString();
        }

        // Step 1: Handles normal cases.
        var longestPalindromeSubstring = string.Empty;

        for (var index = 0; index < s.Length && s.Length - index > longestPalindromeSubstring.Length; index++)
        {
            var currentChar = s[index];
            var currentCharLastIndex = s.LastIndexOf(currentChar);

            if (index == currentCharLastIndex)
            {
                if (!string.IsNullOrWhiteSpace(longestPalindromeSubstring) ||
                        longestPalindromeSubstring.Length > 1)
                {
                    continue;
                }

                longestPalindromeSubstring = currentChar.ToString();
            }

            var currentCharIndexes = new Stack<int>();

            for (var nextIndex = index + 1; nextIndex <= currentCharLastIndex; nextIndex++)
            {
                if (s[nextIndex] == currentChar)
                {
                    currentCharIndexes.Push(nextIndex);
                }
            }

            while (currentCharIndexes.Any())
            {
                var relatedIndex = currentCharIndexes.Pop();
                var possibleStr = s.Substring(index, relatedIndex - index + 1);
                var reversedPossibleStr = new string(possibleStr.Reverse().ToArray());

                if (!possibleStr.Equals(reversedPossibleStr) ||
                    possibleStr.Length < longestPalindromeSubstring.Length ||
                    possibleStr.Equals(longestPalindromeSubstring))
                {
                    continue;
                }

                longestPalindromeSubstring = possibleStr;
            }
        }

        return longestPalindromeSubstring;
    }

However this solution above was failed to pass the LeetCode validation since the issue: Time Limit Exceeded.
Then I just made a small update, and the solution version 2 passed, the changed part was only adding ToCharArray() method before invoking Reverse() method:

var reversedPossibleStr = new string(possibleStr.ToCharArray().Reverse().ToArray());

if (!possibleStr.Equals(reversedPossibleStr) ||
     possibleStr.Length < longestPalindromeSubstring.Length ||
     possibleStr.Equals(longestPalindromeSubstring))
{
     continue;
}
…………

But I am not sure the reason why it can work, I just guessed that the data in an array will be arranged in a sequence memory space, it may help to improve the performance, could someone explain more detail.
Thank you in advance.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

The Reverse method uses EnumerableHelpers.ToArray to fetch the count of the input enumerable. If the enumerable doesn’t implement ICollection<T> interface, it will use a list-like approach to creates an array which will extend the array many times. Unfortunately string doesn’t implement ICollection<char>, though it knows how many characters it contains, so string.Reverse() is slower than string.ToCharArray().Reverse().

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading