Java string-manipulation problem !

Question

I must write a function that takes two words (strings) as arguments, and determines if the first word can be transformed into the second word using only one first-order transformation.

• First-order transformations alter only one letter in a word

• The allowed transformations are: insert, remove and replace

  • insert = insert a letter at any position in the word
  • remove = delete a letter from any position in the word
  • replace = replace a letter with another one

Any suggestions? Any Java examples would be great!

Answer 1

You can use the Levenshtein distance and only allow distances of 1 (which means, one char must be altered). There are several implementations just google "Levenshtein java" or so.

The other "not so smart" but working thing would be the good old brute force. Just try out every situation with every char and you get what you want. :-)

Answer 2

Think: If you're only allowed a single transformation, then the difference in length between the "before" and "after" words should give you a very strong hint as to which of those three transformations has any chance of being successful. By the same token, you can tell at a glance which transformations will be simply impossible.

Once you've decided on which transformation, the rest of the problem becomes a job for Brute Force Man and his sidekick, Looping Lady.

Answer 3

This does look like homework so I'm not going to give you the answer, but any time you approach a problem like this the best thing to do is start sketching out some ideas. Break the problem down into smaller chunks, and then it becomes easier to solve.

For example, let's look at the insert operation. To insert an letter, what is that going to do to the length of the word in which we are inserting the letter? Increase it or decrease it? If we increase the length of the word, and the length of this new word is not equal to the length of the word we are trying to match, then what does that tell you? So one condition here is that if you are going to perform an insert operation on the first word to make it match the second word, then there is a known length that the first word must be.

You can apply similar ideas to the other 2 operations.

So once you establish these conditions, it becomes easier to develop an algorithm to solve the problem.

The important thing in any type of assignment like this is to think through it. Don't just ask somebody, "give me the code", you learn nothing like that. When you get stuck, it's ok to ask for help (but show us what you've done so far), but the purpose of homework is to learn.

Answer 4

It's not a homework, this is a real world problem !

Answer 5

If you need to check if there is one and exactly one edit from s1 to s2, then this is very easy to check with a simple linear scan.

• If both have the same length, then there must be exactly one index where the two differ
  • They must agree up to a common longest prefix, then skipping exactly one character from both, they must then agree on a common suffix
• If one is shorter than the other, then the difference in length must be exactly one
  • They must agree up to a common longest prefix, then skipping exactly one character from the longer one, they must then agree on a common suffix

If you also allow zero edit from s1 to s2, then simply check if they're equal.

Here's a Java implementation:

static int firstDifference(String s1, String s2, int L) {
    for (int i = 0; i < L; i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            return i;
        }
    }
    return L;
}
static boolean oneEdit(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return oneEdit(s2, s1);
    }
    final int L = s1.length();
    final int index = firstDifference(s1, s2, L);
    if (s1.length() == s2.length() && index != L) {
        return s1.substring(index+1).equals(s2.substring(index+1));
    } else if (s2.length() == L + 1) {
        return s1.substring(index).equals(s2.substring(index+1));
    } else {
        return false;
    }
}

Then we can test it as follows:

    String[][] tests = {
        { "1", "" },
        { "123", "" },
        { "this", "that" },
        { "tit", "tat" },
        { "word", "sword" },
        { "desert", "dessert" },
        { "lulz", "lul" },
        { "same", "same" },
    };
    for (String[] test : tests) {
        System.out.printf("[%s|%s] = %s%n",
            test[0], test[1], oneEdit(test[0], test[1])
        );
    }

This prints (as seen on ideone.com):

[1|] = true
[123|] = false
[this|that] = false
[tit|tat] = true
[word|sword] = true
[desert|dessert] = true
[lulz|lul] = true
[same|same] = false