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.

• Turing85: Looks like you are looking for an edit dinstance not larger than one. I have a hunch that it should be possible in O(n+m), where n and m are the lenghts of the two Strings. If the code works, the question might be better suited for Code Review.

Answer 1

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("", ""));
}

• itaik: Very nice, can you explain the last if statement? if((offset==1) &&...))
• RubenDG: @itaik If offset == 0 (everytime the strings have the same length), I can skip that check. If the character at index i of the shorstest string doesn't match with the the one at the same index of the longest string, I'll compare it with the one at index i+1 (i+offset), but such compare is valid only if i+1 is a valid index, so I have to check ((i + offset) < longest.length). If (shortest[i] != longest[i + offset]), there is no need to go further, because there are at least two different characters, so I can return false

Answer 2

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

• itaik: Can you explain your solution? I don't really understand why you compare s1.length and s2.charAt? is this a mistake? you return false every time I check

Answer 3

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

}

• itaik: It looks like this solution only be right if the strings are in the same order. If we will try this example: abc, cba => your solution will return "OK", because you will replace each letter with an empty string, but as you can see, we need to change more then 1 letter (a AND c).
• Andrea Annibali: I didn't get it, I thought that position wouldn't be important. I edited my solution, now I think is correct.

Answer 4

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

• itaik: This is a nice approach but please notice that your solution can be tricky because you only check the number of times each letter is shown, remember that you also need to make sure you only need to make 1 change, so if we take those strings: abcd, afbd, your solution will work and return true (because in "letters count" we only have differents in 'c' and 'f'), but it should return false because we need to change 'f' AND 'b' (if we look at the second string)
• user10762593: This approach makes the erroneous assumption that char values are 8 bit. Actually, the arrays need to be 64K (and even then it doesn't handle UTF16 surrogates properly). The world is not ASCII.
• Sunil Dabburi: Thank you guys for the feedback. That’s true. I will update my code.

Answer 5

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