# 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;

namespace ConsoleApplication2
{

public class Program
{
public static void Main()
{
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)
{
}

foreach (var c in stringToCheck2)
{
}

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;
}
}
}
}

• ..and find my bugs - fair enough, but does it work as intended? – Mathieu Guindon Dec 3 '14 at 21:20
• Why do all the Math.Abs() instead of s1.Length != s2.Length? – krillgar Dec 3 '14 at 21:21
• yes, it is compiling and running, with some small tests i have made – Gilad Dec 3 '14 at 21:22
• @krillgar it suppose to check for a difference bigger than one. so "gilad" and "gilada" still return true, but "giladaa" will not – Gilad Dec 3 '14 at 21:24
• Ah, good point. I didn't think of that part. But shouldn't that be > 1 then? Because if it differs by two, then it will not be caught there. – krillgar Dec 3 '14 at 21:25

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 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)
{
}


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(n\log n)$

• Great Answer! thanks I didn't even thought about complexity. – Gilad Dec 3 '14 at 21:32
• updated my answer, this is what you meant? – Gilad Dec 3 '14 at 21:37
• @Gilad: don't change your question. You can always post a followup question once you've incorporated the changes but changing it here invalidates answers. – Jeroen Vannevel Dec 3 '14 at 21:50

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;
}

• can you say what is the complexity of this? – Gilad Dec 3 '14 at 23:15
• @Gilad -Near as I can tell Except is O(n) and Count is O(1). – tinstaafl Dec 3 '14 at 23:55
• There's a bug: CompareStrings("a", "a ") returns false (while CompareStrings("a", "ax") returns true, as expected). – mjolka Dec 4 '14 at 0:13
• @Gilad - Oops missed that. It's fixed now. – tinstaafl Dec 4 '14 at 0:22
• Sorry to be that guy, but there's another bug: "aabc", "abd" returns true. – mjolka Dec 4 '14 at 0:38