Compare 2 String with condition

Question

I try to compare 2 strings in JAVA and check if they are the same, but with a special condition: both strings are the same up to the difference of one letter (you can add/remove/change that letter)

abc, abcd -> good (remove 'd')

abcd, abd -> good (add 'c')

abcd, abdd -> good (change 'd')

abc, abdd -> bad (need to remove and change more than 1 letter)

abcd, abfde -> bad (need to change 'f' and add remove 'e')

My idea was to run on both strings together and compare each letter every time, and when I find a "problem" I only advanced with 1 string if one string is longer then the other (let's say: abcde, abde => a,a -> b,b -> c,d -> d,d -> e,e)

But for some reason, I couldn't get it right. Feel too much if-else in my code.

public boolean sameString(String s1, String s2) {
    if(Math.abs(s1.length()-s2.length()) > 1) {
        return false;
    }
    else {
        int i = 0;
        int j = 0;
        int count = 0;
        while(i != s1.length() && j != s2.length()) {
            if(s1.charAt(i) != s2.charAt(j)) {
                count++;
                if(s1.length() == s2.length()) {
                    i++;
                    j++;
                }
                else if(s1.length() > s2.length()) {
                    i++;                    
                }else {
                    j++;
                }
            }else {
                if(i < s1.length()) {
                    i++;                    
                }
                if(j < s2.length()) {
                    j++;                    
                }                   
            }
        }
        if(count > 1) {
            return false;
        }
        return true;
    }
}

Someone can help optimize it? I'm pretty sure there is a better way to solve this.

Thanks.

Answer 1

Here is the solution I tried:

public class Test {

    public static void main(String[] args) {

        System.out.println(compareStrings("abc", "abcd")); // true
        System.out.println(compareStrings("abcd", "abd")); //
        System.out.println(compareStrings("abcd", "abdd"));
        System.out.println(compareStrings("abc", "abdd"));
        System.out.println(compareStrings("abcd", "abfde"));
        System.out.println(compareStrings("abcd", "afbd"));
        System.out.println(compareStrings("a", ""));
        System.out.println(compareStrings("", "a"));
        System.out.println(compareStrings("abc", "abc"));
        System.out.println(compareStrings("a", "a"));
    }

    private static boolean compareStrings(String first, String second) {

        if (Math.abs(first.length() - second.length()) > 1) {
            return false;
        }

        int mismatchCount = 0;
        int i = 0;
        int j = 0;
        while (i < first.length() && j < second.length()) {
            if (first.charAt(i) != second.charAt(j)) {
                if (mismatchCount == 1) {
                    return false;
                }
                mismatchCount++;
                if (first.length() > second.length()) {
                    i++;
                } else if (first.length() < second.length()) {
                    j++;
                } else {
                    i++;
                    j++;
                }
            } else {
                i++;
                j++;
            }
        }

        // for extra character left
        if (i < first.length() || j < second.length()) {
            mismatchCount++;
        }

        return mismatchCount <= 1;
    }
}

Output:

true
true
true
false
false
false
true
true
true
true

Answer 2

I think the following is a much simpler solution:

public class StrTest {

public static void eval(String a, String b) {
    if (a.length() > b.length()) {
        String c = b;
        b = a;
        a = c;
    }
    if (a.length() <= b.length()) {
        int i=0; char[] tmp = b.toCharArray();
        for (char c : a.toCharArray()) {
            if (tmp[i] == c) {
                tmp[i]= ' ';
            }
            i++;
        }
        b = new String(tmp).trim();
    }
    System.out.println(b.length() > 1 ? "KO" : "OK");
}

public static void main(String[] arg) {
    String a = "cba";
    String b = "abcd";
    eval(a, b);
}

}

Answer 3

I suggest another concise answer:

public class StrTest {

    public static void eval(String a, String b) {
        StringBuilder s1 = new StringBuilder(a.length() > b.length() ? b : a);
        StringBuilder s2 = new StringBuilder(a.length() > b.length() ? a : b);

        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(i)) {
                s2.setCharAt(i, ' ');
            }
        }
        System.out.println(new String(s2).trim().length() > 1 ? "KO" : "OK");
    }

    public static void main(String[] arg) {      
        String a = "abc";
        String b = "abcd";
        eval(a, b);
    }
}

Answer 4

you have to try something like this

public boolean sameString(String s1, String s2) {
   if (Math.abs(s1.length() - s2.length()) > 1) {
      return false;
   } else {
      int i = 0;
      int j = 0;
      while (i < s1.length() && j <  s2.length()) {
         if(Math.abs(i-j)>1) {
            return false;
         } else if (s1.charAt(i) != s2.charAt(j)) {
            if (s1.length()>s2.charAt(j)) {
               i++;
               continue;
            } else if (s1.length()<s2.charAt(j)){
               j++;
               continue;
            }
            return false;
         }
         i++;
         j++;
      }
      if(i < s1.length() || j < s2.length()) {
         return false;
      }
      return true;
   }
}

Answer 5

You can add && (count < 2) in your while condition: while ((i != s1.length()) && (j != s2.length()) && (count < 2)) {.
You are calling .length() several times inside the loop. You call call it just once per string and store the result.
Moreover if you have to return a boolean, you can return just the if expression. I mean: instead of if (something) return true; you could simply do return (something);
Lastly if you're going to test that method against long strings, you could take advantage of toCharArray() in order to avoid calling .charAt() inside the loop.

Try this:

public static boolean sameString(final String s1, final String s2) {
    final int s1Len = s1.length();
    final int s2Len = s2.length();
    if (Math.abs(s1Len - s2Len) > 1) {
        return false;
    }

    // if the strings are long enough, using char[] may save up time
    char[] shortest, longest; 
    if (s1Len <= s2Len) {
        shortest = s1.toCharArray();
        longest = s2.toCharArray();
    } else {
        shortest = s2.toCharArray();
        longest = s1.toCharArray();
    }

    int diff = 0;
    int offset = 0;
    // if there are at least 2 different characters, there is no need to check more
    for (int i = 0; (i < shortest.length) && (diff < 2) && ((i + offset) < longest.length); i++) {
        if (shortest[i] != longest[i + offset]) {
            diff++;
            if (s1Len != s2Len) {
                offset++;
            }
            if ((offset == 1) && ((i + offset) < longest.length) && (shortest[i] != longest[i + offset])) {
                return false;
            }
        }
    }

    return (diff < 2);
}

// that's how I tested it
public static void main(final String[] args) {

    System.out.println(sameString("abc", "abcd"));
    System.out.println(sameString("bcd", "abcd"));
    System.out.println(sameString("acd", "abcd"));
    System.out.println(sameString("abcd", "abdd"));
    System.out.println(sameString("abc", "abdd"));
    System.out.println(sameString("abcd", "abfde"));
    System.out.println(sameString("abcde", "acde"));
    System.out.println(sameString("abcde", "acdee"));
    System.out.println(sameString("abcde", "aced"));
    System.out.println(sameString("a", ""));
    System.out.println(sameString("", ""));
}