I have a method who checks if it is a palindrome or not

public bool IsPalindrome(PalindromeModel model)
    {
        // First, check whether input string is null or whitespace.
        // If yes, then return false.
        if (string.IsNullOrWhiteSpace(model.Value))
            return false;

        var inputDict = new Dictionary<char, int>();

        // Big/small letter is not important
        var lowerInputStr = model.Value.ToLower();

        // Fill input dictionary
        // If hit a space, then skip it
        for (var i = 0; i < lowerInputStr.Length; i  )
        {
            if (lowerInputStr[i] != ' ')
            {
                if (inputDict.ContainsKey(lowerInputStr[i]))
                    inputDict[lowerInputStr[i]]  = 1;
                else
                    inputDict.Add(lowerInputStr[i], 1);
            }
        }

        var countOdds = 0;
        foreach (var elem in inputDict)
        {
            if (elem.Value % 2 != 0)
                countOdds  ;
        }

        return countOdds <= 1;

     }

So it works with this words: dood, A Santa Lived As a Devil At NASA

But for more complex palindromes like Mr. Owl Ate My Metal Worm it returns false, but it should be true, how can I achieve this?

CodePudding user response：

Remove the spaces and the punctuations before the first loop

var lowerInputStr = new string(model.Value
                      .ToCharArray()
                      .Where(c => !char.IsPunctuation(c)).ToArray())
                      .ToLower()
                      .Replace(" ", "");

CodePudding user response：

That solution looks overly complex. I'd just walk in from both edges, skipping over any characters you don't define as being in scope for comparison. In this implementation, I only consider letters while ignoring case. Note that the solution doesn't allocate any additional memory (as for example string.Replace() or string.ToLower() do internally) and runs worst case input (it is a palendrome) in O(N).

bool IsPalendrome(string input)
{
    var left = 0;
    var right = input.Length - 1;

    while (left < right)
    {
        left = SkipNonLetters(input, left, 1);
        right = SkipNonLetters(input, right, -1);
        
        if (char.ToUpperInvariant(input[left]) != char.ToUpperInvariant(input[right]))
            return false;
            
        left  ;
        right--;
    }
    
    return true;
}

int SkipNonLetters(string input, int startAt, int direction)
{
    while (startAt >= 0 && startAt < input.Length && !char.IsLetter(input[startAt]))
        startAt  = direction;
        
    return startAt;
}

Examples:

Console.WriteLine(IsPalendrome("dood"));
Console.WriteLine(IsPalendrome("A Santa Lived As a Devil At NASA"));
Console.WriteLine(IsPalendrome("Mr. Owl Ate My Metal Worm"));

Output:

True
True
True

CodePudding user response：

To expand on what Muhammad Sulaiman said, after you have the string cleaned up, the rest of the method can be a lot simpler

var lowerInputStr = new string(input.ToCharArray()
     .Where(c => !char.IsPunctuation(c))
     .ToArray())
     .ToLower()
     .Replace(" ", ""); 
    
return lowerInputStr.Substring(lowerInputStr.Length / 2) == (new String(lowerInputStr.Reverse().ToArray()))
.Substring(lowerInputStr.Length / 2);