One character diff – string comparison

The question was:

Create an algorithm to check if two strings differ by one character.

This wasn’t my interview, so I tried to understand the question.

Options:

1. just compare the chars one by one, I assume the lower case and uppercase isn’t the same.

2. compare the chars in any given order meaning “tube” and “bute” are the same…

Please be as strict as you can and find my bugs.

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

namespace ConsoleApplication2
{   

    public class Program
    {
        public static void Main()
        {
            Console.WriteLine("Please Enter some text");    
            string stringToCheck1 = "Out";
            string stringToCheck2 = "tuo";

            bool result = CompareStrings(stringToCheck1, stringToCheck2);
            PrintMessage(result);
            result = CompareAllLetters(stringToCheck1, stringToCheck2);
            PrintMessage(result);
        }
        public void PrintMessage(bool result)
        {
            if (result)
            {
                Console.WriteLine("Strings are less than one letter apart");
                return;
            }
            Console.WriteLine("Strings are more than one letter apart");            
        }

        //checks if the letters one by one
        public static bool CompareStrings(string stringToCheck1, string stringToCheck2)
        {
            //check if strings are not the same size 
            if (Math.Abs(stringToCheck2.Length - stringToCheck1.Length) > 2)
            {
                return false;
            }

            int counter = 0;
            for (int i = 0; i < stringToCheck1.Length; i++)
            {
                if (stringToCheck1[i] != stringToCheck2[i])
                {
                    counter++;
                }
            }
            if (counter > 1)
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        //checks if the letters in any order
        public static bool CompareAllLetters(string stringToCheck1, string stringToCheck2)
        {
            //check if strings are not the same size 
            if (Math.Abs(stringToCheck2.Length - stringToCheck1.Length) > 2)
            {
                return false;
            }

            List<char> string1LettersList = new List<char>();
            List<char> string2LettersList = new List<char>();
            foreach (var c in stringToCheck1)
            {
                string1LettersList.Add(c);
            }

            foreach (var c in stringToCheck2)
            {
                string2LettersList.Add(c);
            }

            for (int i = 0; i < string1LettersList.Count; i++)
            {
                if (string2LettersList.Contains(string1LettersList[i]))
                {
                    string2LettersList.Remove(string1LettersList[i]);
                }
            }
            if (string2LettersList.Count > 2)
            {
                return false;
            }
            else
            {
                return true;
            }    
        }
    }
}

Naming

CompareStrings() and CompareAllLetters are poorly named. You need a comment to explain what the methods should achieve.

The input parameters string stringToCheck1, string stringToCheck2 are also poorly named using some kind of hungarian style.

The input parameter of the PrintMessage() method is also poorly named. It is just not obvious what result should mean.

The same is true for the local variables string1LettersList and string2LettersList.

Comments

Comments should describe why something is done. The code should describe what is done.
This is especially true if the comment is plain wrong like //check if strings are not the same size. The check in question is not if they have a different size or not, it checks if the difference in length is greater than 2.

Simplifications

• Use built in methods to simplify things.

  Like this

  List<char> string1LettersList = new List<char>();
  foreach (var c in stringToCheck1)
  {
      string1LettersList.Add(c);
  }
  

  can be simplified to

  List<char> string1LettersList = stringToCheck1.ToList<char>();  
  

• returning booleans

  Like already mentioned in vnp‘s answer you can simplify the returning of booleans. This is true for both of your methods.

  The condition in the CompareStrings() method is obviously flawed. If both strings are equal, it would return true, so better change it to

  return (counter == 1);  
  

• exit early

  You already do a check at the top of the methods (also it is done wrong), you can add another check for checking if both strings are the same.

  In the CompareStrings() method you can exit early if before the incremention counter == 1 like

  for (int i = 0; i < stringToCheck1.Length; i++)
  {
      if (stringToCheck1[i] != stringToCheck2[i])
      {
          if (counter == 1) { return false; }
          counter++;
      }
  } 
  

Code duplication

In both methods you have the same (wrong) check about the size difference of the strings. You should extract this check to a separate method in which you also can integreate the check if both strings are the same.

private bool IsComparisonNeeded(String first, String second)
{
    if (first == second) { return false; }
    if (first == null || second == null) { return false; }

    return (Math.Abs(first.Length - second.Length) < 2);
}  

Bugs

• if strings are same, both methods returns true
• if one or both of the strings is null the application crashes
• if the difference in CompareAllLetters() is 2 it returns true

Refacoring

Can’t be done right now, because

• the code isn’t producing the expected output
• it is not clear for which input which output should be expected.

Suggestion

For a problem like this, you should first write tests defining the expected behaviour.

I am not a C# expert, and leave an idiomatic review to those who are. Two general mistakes however strike immediately:

• Redundant logic

  if (condition)
      return false;
  else
      return true
  

  is equivalent to a single line

  return !condition;
  

• Time complexity

  The nested loops in CompareAllLetters make the complexity quadratic. Sorting the lists prior to compare drives complexity down to $O(nlog n)$

Here’s a relatively simple way using LINQ:

bool CompareStrings(string a, string b)
{
    int diff = a.Except(b).Count();
    if(a.Length != b.Length)
    {
        if(Math.Abs(a.Length - b.Length) > 1)
        {
            return false;
        }
        if (b.Length > a.Length && diff == 0)
        {
            return true;
        }
    }
    return diff == 1;
}